链表是一种物理存储单元上并不要求连续的存储结构(当然也可以连续的,数组要求必须连续),链表中数据元素之间的逻辑顺序,是通过链表中的指针指向进行实现的(逻辑上相邻但物理上不一定相邻,数组中逻辑和物理上都相邻),如图所示:
其中:链表结构中,为了表示每个数据元素与其直接后继数据元素之间的逻辑关系,除了要存储其本身的数据之外,还需存储一个指针,用于指向其直接后继元素(其实是直接后继的存储位置),这两部分信息就是我们所说的一个结点元素。多个节点元素通过指针域建立关系并形成链表。
链表也分为好几种,常见的有单向链表,单向循环链表,双向链表,双向循环链表。
最简单的一种链表,每一个节点(Node)除了存储数据之外,只有一个指针(后继指针,也称引用)指向后面一个节点(Node),这个链表称为单向链表。其基本形态如图所示:
对于”单链表”而言,有两个节点比较特殊,分别是第一个节点和最后一个节点。我们一般习惯于将第一个节点称为“头节点”(head),最后一个节点称为“尾节点”(tail)。“头节点”一般用于记录链表的基地址,通过此地址获取链表中的节点对象。“尾节点”的指针域不指向任何节点,指针域的值为null,表示最后一个节点。
class Node{
Object data;
Node next;
Node(Object element, Node next) {
this.data= element;
this.next = next;
}
}
循环链表就是一种特殊的单向链表,只不过在单向链表的基础上,将尾节点的指针指向了Head节点,使之首尾相连。如图所示:
单向循环链表相对于单向链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时,就特别适合采用单向循环链表,这样可以很大程度上减少代码量。
双向链表与单向链表的区别是前者是2个方向都有指针,后者只有1个方向的指针。双向链表的每一个节点都有2个指针,一个指向前驱节点,一个指向后继节点。如图所示:
双向链表相对于单向链表,需要额外的一个空间来存储前驱结点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。但双向链表支持双向遍历,这样也带来了双向链表操作的灵活性。例如,单从结构上来看,双向链表可以支持O(1)时间复杂度的情况下找到前驱结点,正是这样的特点,也使双向链表在某些情况下的插入、删除等操作都要比单向链表更加简单和高效。
class Node {
Object element;
Node next;
Node pre;
Node(Object element, Node pre,Node next) {
this.element= element;
this.pre= pre;
this.next = next;
}
}
双向循环链表只是在双向链表的基础上,添加了头节点与尾节点的双向引用,如图所示:
说明:双向循环链表可以从任意节点开始向前或向后查找节点。
链表的优势并不在与访问,因为链表无法通过首地址和下标去计算出某一个节点的地址,所以链表中如果要查找某个节点,则需要一个节点一个节点的遍历,因此链表的访问时间复杂度为O(n),但对于双向链表而言,假如已经确定某个节点的位置,再去查找其上个节点的位置,可以直接通过前驱指针直接获取上一个点对象地址即可,这一些要比单向链表有优势。
我们知道在进行数组的插入、删除操作时,为了保持内存数据的连续性,需要做大量的数据移动,所以时间复杂度是O(n)。而在链表中插入或者删除一个数据,我们并不需要为了保持内存的连续性而移动节点,因为链表中节点的存储空间本身就不需要连续。所以,在链表中插入和删除一个节点时是非常快速的。我们只需要修改指针的指向即可。
链表中节点的插入,如下图所示:
链表中节点的删除,如下图所示:
对于链表而言,无论是执行插入还是删除操作,他们的时间复杂度可以理解为O(1)。但是在插入和删除之前,需要遍历查找的时间复杂度为O(n)。根据时间复杂度分析中的加法法则,插入或删除某个值的结点时,对应的总时间复杂度仍旧为O(n)。
package com.cy.pj.ds.linked;
import java.util.NoSuchElementException;
public class SimpleSingleLinkedList {
//头节点
private Node head;
//记录有效元素的个数
private int size;
//每一个节点的类型
class Node{
Object data;
Node next;
public Node(Object data) {
this.data=data;
}
}
public Node getHead() {
return head;
}
//定义向链表头部位置添加节点的方法
public void addFirst(Object data) {
//1.create new node
Node newNode=new Node(data);
//2.make next of new node as head
newNode.next=head;
//3.move the head to new node;
head=newNode;
//4.update size
size++;
}
//定义在链表尾部添加新节点的方法
public void addLast(Object data) {
//1.创建新节点
Node newNode=new Node(data);
//2.判定头节点是否为空,假如头节点为空则当前节点应该为头节点
if(head==null) {head=newNode;return;}
//3.获取链表中的最后一个节点
Node last=head;
while(last.next!=null)last=last.next;
//4.设置最后一个节点的next节点为当前的新节点
last.next=newNode;
//5.更新size的值
size++;
}
//定义在指定位置添加新的节点
public void add(int index,Object data) {
//检查index的范围
if(index<0||index>size)
throw new IndexOutOfBoundsException();
//添加头部节点(index==0)
if(index==0) {addFirst(data);return;}
//添加尾部节点(index==size)
if(index==size) {addLast(data);return;}
//查找index-1位置的节点,并在index位置添加新节点
Node preNode=node(index-1);
Node newNode=new Node(data);
newNode.next=preNode.next;
preNode.next=newNode;
//更新size的值。
size++;
}
//按位置查找节点
Node node(int index) {
Node node=head;
for(int i=0;i<index;i++) {
node=node.next;
}
return node;
}
//===================remove node============
//移除头部节点
public void removeFirst() {
if(size==0||head==null)
throw new NoSuchElementException();
head=head.next;
size--;
}
//移除尾部节点
public void removeLast() {
if(size==0||head==null)
throw new NoSuchElementException();
if(size==1) {
head=null;
}else {
Node preNode=node(size-2);
preNode.next=null;
}
size--;
}
//按指定位置移除节点
public void removeNode(int index) {
//1.越界检查
if(index<0||index>=size)
throw new IndexOutOfBoundsException();
//2.判定是否为头节点并移除
if(index==0) {
removeFirst();
return;
}
//3.判定是否为尾节点并移除。
if(index==size-1) {
removeLast();
return;
}
//4.查找节点进行移除。
Node preNode=node(index-1);
preNode.next=preNode.next.next;
//5.修改size的值
size--;
}
//基于节点data属性值移除节点对象
public void removeNode(Object data) {
//1.获得head节点并进行判定和移除
Node temp=head,pre=null;
if(temp!=null&&temp.data.equals(data)) {
head=temp.next;
size--;
return;
}
//2.查找对应节点
while(temp!=null&&!temp.data.equals(data)){
pre=temp;
temp=temp.next;
}
if(temp==null)return;
//3.移除节点
pre.next=temp.next;
//4.更新size的值
size--;
}
@Override
public String toString() {
StringBuilder sb=new StringBuilder("[");
Node node=head;
while(node!=null) {
sb.append(node.data).append(",");
node=node.next;
}
if(sb.length()>1)sb.deleteCharAt(sb.length()-1);
sb.append("]");
return sb.toString();
}
public int size() {
return size;
}
public static void main(String[] args) {
//doTestAddRemove();
doTestContainsLoop();
}
private static void doTestContainsLoop() {
SimpleSingleLinkedList list=new SimpleSingleLinkedList();
list.addFirst(100);
list.addFirst(200);
list.addFirst(300);
System.out.println(list);//300,200,100
list.detactLoop();
list.head.next.next.next=list.head;
list.detactLoop();
}
private static void doTestAddRemove() {
SimpleSingleLinkedList list=new SimpleSingleLinkedList();
list.addFirst(100);
list.addFirst(200);
list.addFirst(300);
System.out.println(list);//[300,200,100]
list.addLast(400);
System.out.println(list);//[300,200,100,400]
list.add(1, 500);
System.out.println(list);//[300,500,200,100,400]
list.removeFirst();
System.out.println(list);//[500,200,100,400]
list.removeLast();//
System.out.println(list);//[500,200,100]
list.removeNode(1);//index
System.out.println(list);//[500,100]
list.removeNode((Object)100);//data
System.out.println(list);//[500]
}
}
package com.cy.pj.ds.linked;
import java.util.NoSuchElementException;
public class SimpleDoubleLinkedList {
//first of node
private Node first;
//last of node
private Node last;
//number of elements
private int size;
//the type of node
class Node{
//store the object
Object element;
//prev of the node;
Node prev;
//next of the node
Node next;
public Node( Node prev, Object element, Node next) {
this.element=element;
this.prev=prev;
this.next=next;
}
}
//添加头节点
public void addFirst(Object element) {
//1.存储第一个节点(后续要修改节点)
Node f=first;
//2.创建新节点
Node newNode=new Node(null, element, f);
//3.设置新的头节点
first=newNode;
//4.对首届点进行判定
if(f==null) {
last=newNode;
}else {
f.prev=newNode;
}
//5.更新size的值
size++;
}
//在链表尾部添加新节点
public void addLast(Object element) {
Node l=last;
Node newNode=new Node(l, element,null);
last=newNode;
if(l==null) {
first=newNode;
}else {
l.next=newNode;
}
size++;
}
//在指定位置添加节点
public void add(int index,Object element) {
if(index<0||index>size)
throw new IndexOutOfBoundsException();
if(index==size) {
addLast(element);
}else {//index>=0 and index
//seach node
Node searchNode=node(index);
Node pred=searchNode.prev;
Node newNode=new Node(pred, element, searchNode);
searchNode.prev=newNode;
if(pred==null) {
first=newNode;
}else {
pred.next=newNode;
}
size++;
}
}
//search node
Node node(int index) {
if(index<(size>>1)) {
Node x=first;
for(int i=0;i<index;i++) {//从前向后
x=x.next;
}
return x;
}else {
Node x=last;
for(int i=size-1;i>index;i--) {//从后向前
x=x.prev;
}
return x;
}
}
//定义删除头节点的方法
public Object removeFirst() {
//1.获取头节点
Node f=first;
if(f==null)
throw new NoSuchElementException();
//2.获取头节点的数据
Object element=f.element;
//3.获取头节点的下一个节点,并修改此节点为头节点
Node next=f.next;
f.element=null;//可以更好的进行gc;
f.next=null;
first=next;
if(next==null) {
last=null;
}else {
next.prev=null;//first
}
//4.更新size的值
size--;
return element;
}
//定义移除尾节点的方法
public Object removeLast() {
//1.获取尾节点
Node l=last;
if(l==null)
throw new NoSuchElementException();
//2.获取最后节点的element值
Object element=l.element;
//3.删除,修改最后节点
Node prev=l.prev;
l.element=null;
l.prev=null;
last=prev;
if(prev==null)first=null;
else prev.next=null;
//4.修改size的值
size--;
return element;
}
//按指定位置移除元素节点
public Object removeObject(int index) {
if(index<0||index>=size)
throw new IndexOutOfBoundsException();
return unlink(node(index));
}
//从链表中卸载某个节点
public Object unlink(Node x) {
//1.存储节点元素值;
Object element=x.element;
//2.获取当前节点的下一个节点和上节点
Node next=x.next;
Node prev=x.prev;
//3.修改节点指向
if(prev==null) {
first=next;
}else {
prev.next=next;
x.prev=null;
}
if(next==null) {
last=prev;
}else {
next.prev=prev;
x.next=null;
}
//修改size的值;
size--;
x.element=null;
return element;
}
//按照对象元素移除节点
public boolean removeObject(Object element) {
if(element==null) {
for(Node x=first;x!=null;x=x.next) {
if(x.element==null) {
unlink(x);
return true;
}
}
}else {
for(Node x=first;x!=null;x=x.next) {
if(x.element.equals(element)) {
unlink(x);
return true;
}
}
}
return false;
}
public static void main(String[] args) {
SimpleDoubleLinkedList list=new SimpleDoubleLinkedList();
list.addFirst(100);//first=100,last=100
list.addFirst(200);//first=200,last=100;
list.addFirst(300);//first=300,last=100
System.out.println(list);//[300,200,100];
list.addLast(400);
System.out.println(list);//[300,200,100,400];
list.add(1, 500);
System.out.println(list);//[300,500,200,100,400];
list.removeFirst();
System.out.println(list);//[500,200,100,400];
list.removeLast();
System.out.println(list);//[500,200,100];
list.removeObject(1);
System.out.println(list);//[500,100];
list.removeObject((Object)100);
System.out.println(list);//[500];
}
@Override
public String toString() {
StringBuilder sb=new StringBuilder("[");
Node node=first;
while(node!=null) {
sb.append(node.element).append(",");
node=node.next;
}
if(sb.length()>1)sb.deleteCharAt(sb.length()-1);
sb.append("]");
return sb.toString();
}
}
需求:初始链表为Input,然后执行reverse后为Output数组结果
Input : list = 1<=>2<=>3<=>4<=>5
reverse
Output : list = 5<=>4<=>3<=>2<=>1
在单项链表中添加如下反转方法:
//实现元素的倒置
public Node reverse(Node curr,Node prev) {
if(curr.next==null) {
head=curr;
curr.next=prev;
return head;
}
Node newPre=curr.next;
curr.next=prev;
reverse(newPre, curr);
return head;
}
在双向链表中添加反转方法:
public void reverse() {
Node temp=null;
Node current=first;
while(current!=null) {
temp=current.prev;
current.prev=current.next;
current.next=temp;
current=current.prev;
}
if(temp!=null) {
first=temp.prev;
}
}
创建测试类,进行链表倒置测试。
package com.cy.pj.ds.linked;
public class SimpleLinkedListReverse {
public static void doTestSingleListReverse() {
SimpleSingleLinkedList list=new SimpleSingleLinkedList();
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addLast(4);
list.addLast(5);
System.out.println(list);//1->2->3->4->5
list.reverse(list.getHead(),null);
System.out.println(list);//5->4->3->2->1
}
public static void doTestDoubleListReverse() {
SimpleDoubleLinkedList list=new SimpleDoubleLinkedList();
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addLast(4);
list.addLast(5);
System.out.println(list);//1->2->3->4->5
list.reverse();
System.out.println(list);//5->4->3->2->1
}
public static void main(String[] args) {
//doTestSingleListReverse();
doTestDoubleListReverse();
}
}
链表本身没有大小的限制,内存无需连续,天然地支持动态扩容,所以插入或删除性能相对较好,尤其是双向链表。但链表的随机访问性能相对较差,因为链表中的数据并非连续存储的,所以无法像数组那样,根据首地址和下标,通过寻址公式就能直接计算出对应的内存地址,而是需要根据指针一个结点一个结点地依次遍历,直到找到相应的结点。
双向链表相对于单向链表最大的优势就是节点的查找速度。对于单链表而言删除某个结点,需要知道其前驱结点b,而单链表并不支持直接获取前驱结点,所以,为了找到前驱结点,我们还是要从头结点开始遍历链表,直到p->next=b,说明p是b的前驱结点。但是对于双向链表来说,这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针,不需要像单链表那样遍历。所以,单链表删除操作需要O(n)的时间复杂度,而双向链表只需要在O(1)的时间复杂度内就搞定了!
需求:定义初始链表,判断如下链表是否有环,并计算环的长度
在单向链表中添加如下如方法:
//计算环中节点个数
int countNodes(Node node) {
int count=1;
Node temp=node;
while(temp.next!=node) {
count++;
temp=temp.next;
}
return count;
}
//测试是否有环
boolean detactLoop() {
Node slow=head,fast=head;
while(slow!=null&&fast!=null&&fast.next!=null) {
slow=slow.next;
fast=fast.next.next;
if(slow==fast) {
System.out.println("Found loop ,nodes.size="+countNodes(slow));
return true;
}
}
return false;
}
添加测试方法,例如:
static void doTestContainsLoop() {
SimpleSingleLinkedList list=
new SimpleSingleLinkedList();
list.addFirst(100);
list.addFirst(200);
list.addFirst(300);
list.head.next.next.next=list.head;
System.out.println(list.detectLoop());
}