数据结构*链表- LinkedList

什么是链表

相较于ArrayList顺序表来说，链表是物理存储结构上非连续存储结构（也就是地址不是连续的）。链表由一系列节点构成，每个节点包含数据和指向下一个节点的引用。链表的各个节点在内存里并非连续存储，而是通过引用相互连接。
节点就相当于下图所示：

value用来存储数据，next用来引用下一个节点。

链表的分类

一共分为三种：单向与双向、带头与不带头、循环与非循环

单向与双向

单向如下图所示：

双向如下图所示：

带头与不带头

带头如下图所示：

不带头如下图所示：

注意：

我在不带头的图中也标记了“head”，这里的意思是链表的第一个数据，这是会变化的（例如：当头插的时候，新增的节点就是“head”了）。而对于带头的来说，head是不会发生变化的，起到一个标记的作用。当头插的时候，只会插在head的后面。也就是说，head的数据是一个无效数据，没有意义。

循环与非循环

循环如下图所示：

非循环如下图所示：

重点学习

由于组合较多，我们主要学习的是单向、不带头、非循环链表和双向、不带头、非循环链表

自己简单实现一个单向、不带头、非循环链表

总的框架：

public interface IMySingleList {//头插法void addFirst(int data);//尾插法void addLast(int data);//插入到指定index下标位置，第一个数据节点为1号下标void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中boolean contains(int key);//删除第一次出现关键字为key的节点void remove(int key);//删除所有值为key的节点void removeAllKey(int key);//得到单链表的长度int size();//清空链表void clear();void display();
}

public class MySingleLinkedList implements IMySingleList{//利用静态内部类，定义节点static class ListNode {public int value;public ListNode next;public ListNode(int value) {this.value = value;}}//定义头节点public ListNode head;//主要是为了理解链表的形成public void creatList() {}@Overridepublic void addFirst(int data) {}@Overridepublic void addLast(int data) {}@Overridepublic void addIndex(int index, int data) {}@Overridepublic boolean contains(int key) {return false;}@Overridepublic void remove(int key) {}@Overridepublic void removeAllKey(int key) {}@Overridepublic int size() {return 0;}@Overridepublic void clear() {}@Overridepublic void display() {}
}

creatList()方法

代码展示：

public void creatList() {ListNode node1 = new ListNode(10);ListNode node2 = new ListNode(20);ListNode node3 = new ListNode(30);ListNode node4 = new ListNode(40);node1.next = node2;node2.next = node3;node3.next = node4;head = node1;
}

代码分析：

ListNode node1 = new ListNode(10);
ListNode node2 = new ListNode(20);
ListNode node3 = new ListNode(30);
ListNode node4 = new ListNode(40);

上述代码是用来创建节点的。

node1.next = node2;
node2.next = node3;
node3.next = node4;

上述代码是用来进行链接的，将一个节点指向另一个节点的引用。

head = node1;

上述代码是将head头节点定义为node1。因为当方法执行完毕，临时变量会被回收，这时候是找不到node1等的其他变量，这时候通过head来找到链表。

通过调试来观察。

display()方法

代码展示：

public void display() {ListNode cur = head;while(cur != null) {System.out.print(cur.value +" ");cur = cur.next;}System.out.println();
}

代码分析：

ListNode cur = head;

上述代码是为了使head保持不变，方法结束后仍能通过head找到链表。

while(cur != null) {System.out.print(cur.value +" ");cur = cur.next;//将cur指向下一个节点
}

上述代码通过while循环实现了value的打印。注意：循环条件一定是cur != null，而不是cur.next != null！！！

总结：while循环条件如果是cur != null，就会遍历所有的节点，cur此时为null；如果条件是cur.next != null，此时最后一个节点不会被遍历，cur.next此时为null。

size()方法

代码展示：

public int size() {int usedSize = 0;ListNode cur = head;while(cur != null) {cur = cur.next;usedSize++;}return usedSize;
}

代码分析：

由于要遍历所有的节点，所以while条件是cur != null。

contains(int key)方法

代码展示：

public boolean contains(int key) {ListNode cur = head;while(cur != null) {if(cur.value == key) {return true;}cur = cur.next;}return false;
}

代码分析：

由于要遍历所有的节点，所以while条件是cur != null。

addFirst(int data)方法

代码展示：

public void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;
}

代码分析：

当链表中没有节点时，也是成立的。head为null，node.next也为null。

addLast(int data)方法

代码展示：

public void addLast(int data) {ListNode cur = head;if(head == null) {addFirst(data);return;}ListNode node = new ListNode(data);while (cur.next != null) {cur = cur.next;}cur.next = node;
}

代码分析：

为了使cur指向最后一个节点（cur不为null），while循环条件就要为cur.next != null。
当链表为空时，cur.next为空（会出现空指针异常）,此时相当于头插，可以直接调用addLast(int data)方法。

addIndex(int index, int data)方法

代码展示：

public void addIndex(int index, int data) {//1、判断当index为1时，即要进行头插if(index == 1) {addFirst(data);return;}//2、判断当index为有效数据+1时，即要进行尾插if(index == size() + 1) {addLast(data);return;}//3、检查index下标合法性checkIndex(index);//4、进行中间节点的插入ListNode node = new ListNode(data);ListNode cur = findIndex(index);node.next = cur.next;cur.next = node;
}
//找到index下标节点的前一个节点
private ListNode findIndex(int index) {ListNode cur = head;int count = index - 2;while (count != 0) {cur = cur.next;count--;}return cur;
}
private void checkIndex(int index) {if(index <= 0 || index > size()) {throw new IndexException("下标位置不合法！");}
}

//自定义异常
public class IndexException extends RuntimeException{public IndexException() {super();}public IndexException(String message) {super(message);}
}

代码分析：

还需要考虑是否为头插、尾插；是否index不合法

remove(int key)方法

代码展示：

public void remove(int key) {//当链表为空时，即无法删除if(head == null) {System.out.println("链表为空，无法删除！");return;}//当链表第一个为要删除的数据，只需要移动head指向if(head.value == key) {head = head.next;return;}//定义要删除节点的前一个节点ListNode cur = search(key);//当没有找到要删除的数据（cur也就是null），直接返回if(cur == null) {System.out.println("链表中没有你要找的数据！");return;}ListNode delete = cur.next;cur.next = delete.next;}
private ListNode search(int key) {ListNode cur = head;while(cur.next != null) {if(cur.next.value == key) {return cur;}cur = cur.next;}//没有找到返回nullreturn null;
}

代码分析：

删除思路如下：

对于找到要删除的节点前一个节点，可以定义一个方法来查找，如下：

removeAllKey(int key)方法

代码展示：

public void removeAllKey(int key) {//当链表为空时，即无法删除if(head == null) {System.out.println("链表为空，无法删除！");return;}ListNode prev = head;ListNode cur = prev.next;while (cur != null) {if(cur.value == key) {prev.next = cur.next;cur = cur.next;}else {prev = prev.next;cur = cur.next;}}//判断头节点if(head.value == key) {head = head.next;}
}

代码分析：

clear()方法

代码展示：

public void clear() {ListNode cur = head;ListNode curN = head;while (cur != null) {cur.value = 0;curN = cur.next;cur.next = null;cur = curN;}//this.head = null;
}

代码分析：

可以直接将头节点置为null，此时后面不再被引用，被回收了；
也可以手动将所有节点置为null。

扩展链表方法

反转链表

要求改变链表结构（达到下图效果），时间复杂度为O(N)。

代码展示：

public void reverseList(ListNode head) {//当链表没有节点，返回if(head == null) {return;}//链表只有一个节点，返回if(head.next == null) {return;}ListNode cur = head.next;head.next = null;while (cur != null) {ListNode curN = cur.next;cur.next = head;head = cur;cur = curN;}
}

代码分析：

只需要将head后面的节点依次头插到head前面，就完成了逆序。
1、
2、

返回链表中间节点。

如果有两个中间节点，则返回第二个节点。

代码展示：

方法一：调用size()方法，返回第size()/2个节点

public ListNode middleNode(ListNode head) {int count = size()/2;ListNode cur = head;while (count != 0) {cur = cur.next;count--;}return cur;
}

方法二：使用快慢指针，让fast走两步，slow走一步，当fast走完了，slow刚好走到中间。

public ListNode middleNode() {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {//while (fast.next != null && fast != null) {  错误fast = fast.next.next;slow = slow.next;}return slow;
}

代码分析：

方法二：

对于方法一以来说，循环了两次，而方法二只循环了一次。

输出倒数第k个节点

代码展示：

方法一：调用size()方法，返回第size() - k + 1个节点

public int kthToLast(ListNode head, int k) {if(k<0 || k > size()) {System.out.println("k值不合法");return -1;}ListNode cur = head;int count = size() -k;while ( count > 0) {cur = cur.next;count--;}return cur.value;
}

方法二：使用快慢指针，让fast先走k - 1步

public int kthToLast(ListNode head, int k) {if(k<0 || head == null) {System.out.println("k值不合法");return -1;}ListNode fast = head;ListNode slow = head;int count = k - 1;while(count > 0) {fast = fast.next;if(fast == null) {return -1;}count--;}while (fast.next != null) {fast = fast.next;slow = slow.next;}return slow.value;
}

代码分析：

方法二只遍历了一遍链表

合并两个升序链表

代码展示：

    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {ListNode headNew = new ListNode(-1);ListNode temp = headNew;while (headA != null && headB != null) {//当有一个链表没有节点了，此时就结束循环了if (headA.val >= headB.val) {temp.next = headB;temp = headB;headB = headB.next;} else {temp.next = headA;temp = headA;headA = headA.next;}}if (headB == null) {//对于headA还有节点temp.next = headA;}if (headA == null) {//对于headB还有节点temp.next = headB;}return headNew.next;//headNew并不是原链表中的节点，返回后面的即可}

代码分析：

链表回文结构判断

代码展示：

public boolean chkPalindrome(ListNode head) {if (head == null) {return true;}//找到中间节点ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}//翻转后半部分链表ListNode cur = slow.next;slow.next = null;while (cur != null) {ListNode curN = cur.next;cur.next = slow;slow = cur;cur = curN;}//让head走到slow，进行比较while (head != slow) {//先进行值的判断if(head.value != slow.value) {return false;}//用于判断偶数情况if(head.next == slow) {return true;}head =head.next;slow = slow.next;}return true;
}

代码分析：

链表分割

给定x，将所有小于x的节点排在其余节点之前，且不能改变原来的数据顺序。

代码展示：

public ListNode partition(ListNode head,int x) {ListNode bStart = null;ListNode bEnd = null;ListNode aStart = null;ListNode aEnd = null;ListNode cur = head;while (cur != null) {if (cur.value < x) {if (bStart == null) {bStart = cur;bEnd = cur;} else {bEnd.next = cur;bEnd = bEnd.next;}} else {if (aStart == null) {aStart = cur;aEnd = cur;}else {aEnd.next = cur;aEnd = aEnd.next;}}cur = cur.next;}//当没有小于x的值时，第一个链表为空if(bStart == null) {return aStart;}//大于等于x的值中最后的节点不一定指向null，可能还指向原链表中的节点，此时需要置为nullif(aEnd != null) {aEnd.next = null;}bEnd.next = aStart;return bStart;
}

代码分析：

找到两个链表公共节点

代码展示：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int lenA = 0;int lenB = 0;ListNode pA = headA;ListNode pB = headB;//计算lenA的值while (pA != null) {lenA++;pA = pA.next;}//计算lenB的值while (pB != null) {lenB++;pB = pB.next;}int len = lenA - lenB;//再次需要遍历链表pA = headA;pB = headB;//这个判断是让pA始终为较长的链表if(len < 0) {pA = headB;pB = headA;len = lenB - lenA;}//让长的pA指向的链表移动len步while (len != 0) {pA = pA.next;len--;}//让两个同时走，当节点相同时，循环结束while (pA != pB) {pA = pA.next;pB = pB.next;}return pA;
}

代码分析：

判断是否为环形链表

代码展示：

public boolean hasCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if(fast == slow) {return true;}}return false;
}

代码分析：

让fast始终比slow快走一步，这样肯定会在环中的某一处相遇。当fast走不了一步或者两步时，链表就没有构成环。

自己简单实现一个双向、不带头、非循环链表

代码展示：

public class MyLinkedList implements IMyLinkedList{static class ListNode{public int value;public ListNode next;public ListNode prev;public ListNode(int value) {this.value = value;}}public ListNode head;public ListNode Last;@Overridepublic void addFirst(int data) {ListNode node = new ListNode(data);if(head == null) {head = node;Last = node;}else {node.next = head;head.prev = node;head = node;}}@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null) {head = node;Last = node;}else {Last.next = node;node.prev = Last;Last = node;}}@Overridepublic void addIndex(int index, int data) {//判断index合法性checkIndex(index);//处理特殊位置if(index == 0) {addFirst(data);return;}if(index == size() - 1) {addLast(data);return;}ListNode cur = search(index);ListNode node = new ListNode(data);//先链接正方向node.next = cur;cur.prev.next = node;//再链接反方向node.prev = cur.prev;cur.prev = node;}private ListNode search(int index) {ListNode cur = head;while (index > 0) {cur = cur.next;index--;}return cur;}private void checkIndex(int index) {if(index < 0 || index >= size()) {throw new IndexException("index下标不合法");}}@Overridepublic boolean contains(int key) {ListNode cur = head;while (cur != null) {if(cur.value == key) {return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {if(head == null){System.out.println("没有数据，无法删除");}ListNode cur = head;while (cur != null) {if(cur.value == key) {//开始删除//1、删除的是头节点if(cur == head) {head = head.next;//下面判断是为了防止链表只有一个节点，访问head.prev会空指针异常if(head != null) {head.prev = null;}}else {//2、当删除的是尾节点if(cur.next == null){cur.prev.next = null;Last = Last.prev;}else {//3、删除的是中间节点cur.prev.next = cur.next;cur.next.prev = cur.prev;}}return;}cur = cur.next;}}@Overridepublic void removeAllKey(int key) {if(head == null){System.out.println("没有数据，无法删除");}ListNode cur = head;while (cur != null) {if(cur.value == key) {//开始删除//1、删除的是头节点if(cur == head) {head = head.next;//下面判断是为了防止链表只有一个节点，访问head.prev会空指针异常if(head != null) {head.prev = null;}}else {//2、当删除的是尾节点if(cur.next == null){cur.prev.next = null;Last = Last.prev;}else {//3、删除的是中间节点cur.prev.next = cur.next;cur.next.prev = cur.prev;}}//return;不返回，继续开始遍历删除key值}cur = cur.next;}}@Overridepublic int size() {ListNode cur = head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void clear() {ListNode cur = head;while(cur != null) {ListNode curN = cur.next;cur.next = null;cur.prev = null;cur = curN;}head = null;Last = null;}@Overridepublic void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.value+" ");cur = cur.next;}System.out.println();}public void redisplay() {ListNode cur = Last;while (cur != null) {System.out.print(cur.value+" ");cur = cur.prev;}System.out.println();}
}

官方提供的链表（双向链表）

构造方法

方法	功能
LinkedList()	无参构造
public LinkedList(Collection<? extends E> c)	使用其他集合容器中的元素构造List

public static void test1() {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.addLast(10);list.addFirst(3);list.add(4);System.out.println(list);System.out.println("-------------");List<Integer> list1 = new LinkedList<>();list1.add(1);list1.add(12);list1.add(13);list1.add(14);list1.add(15);System.out.println(list1);System.out.println("-------------");List<Number> list2 = new LinkedList<>(list1);System.out.println(list2);
}

常用方法

方法	功能
boolean add(E e)	尾插e
void add(int index,E element)	将e插入到index位置
boolean addAll(Collection<? extends E> c)	尾插c中的元素
E remove(int index)	删除index位置元素
boolean remove(Object o)	删除遇到的第一个o
E get(int index)	获取下标index位置元素
E set(int index,E element)	将下标index位置元素设置为element（替换）
void clear()	清空
boolean contains(Object o)	判断o是否在线性表中
int indexOf(Object o)	返回第一个o所在下标
int lastindexOf(Object o)	返回最后一个o所在下标
List<E> subList(int fromIndex,int toIndex)	截取部分list

这些常用方法和ArrayList是一样的，但具体的底层实现过程是完全不一样的。

遍历链表

其中的方法和遍历ArrayList是一样的

public static void test2() {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);System.out.println("--------直接sout输出--------");System.out.println(list);System.out.println("--------for循环遍历--------");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}System.out.println();System.out.println("--------foreach循环遍历--------");for (Integer integer : list) {System.out.print(integer + " ");}System.out.println();System.out.println("--------迭代器正序输出1--------");Iterator<Integer> it = list.listIterator();while (it.hasNext()) {System.out.print(it.next()+" ");}System.out.println();System.out.println("--------迭代器正序输出2--------");ListIterator<Integer> its = list.listIterator();while (its.hasNext()) {System.out.print(its.next()+" ");}System.out.println();System.out.println("--------迭代器正序输出3（从指定下标位置输出）--------");ListIterator<Integer> itss = list.listIterator(2);while (itss.hasNext()) {System.out.print(itss.next()+" ");}System.out.println();System.out.println("--------迭代器逆序输出--------");ListIterator<Integer> reits = list.listIterator(list.size());while (reits.hasPrevious()) {System.out.print(reits.previous()+" ");}
}

链表优缺点

优点

1、插入与删除高效，时间复杂度为O(1)。
2、由于链表的节点在内存中可以是不连续存储的，适合存储分散的数据。

缺点：

1、随机访问效率低，需要通过循环来遍历节点，时间复杂度为O(n)。