目录
一、链表
1.定义
2.分类
二、无头单向非循环链表
1.模拟实现
2.相关题目
三、无头双向链表LinkedList
1.模拟实现
2.LinkedList的使用
3.LinkedList的常用方法
4.LinkedList的遍历
四、ArrayList和LinkedList的区别
五、练习题
链表是一种常见的数据结构，用于存储数据元素的集合。链表由一系列的节点组成，每个节点包含数据和指向下一个节点的指针。链表中的节点可以按照任意顺序存储，每个节点都通过指针与其他节点相连接，形成链式结构。
单向或者双向 、带头或不带头、循环或非循环。
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
无头单向非循环链表是指链表中没有头节点，且链表中的节点只能指向下一个节点，不能回指到前一个节点，也不能形成循环。每个节点包含一个数据域和一个指针域，指针域指向链表中的下一个节点。
Ilist接口：
package demo;public interface IList { //头插法 public void addFirst(int data); //尾插法 public void addLast(int data); //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index, int data); //查找是否包含关键字key是否在单链表当中 public boolean contains(int key); //删除第一次出现关键字为key的节点 public void remove(int key); //删除所有值为key的节点 public void removeAllKey(int key); //得到单链表的长度 public int size(); public void clear(); public void display();}MySinglelist：
package demo;public class MySinglelist implements IList{ static class ListNode{ public int val; public ListNode next; public ListNode(int val) { this.val = val; } } public ListNode head; public void createNode(){ ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); ListNode node3 = new ListNode(3); ListNode node4 = new ListNode(4); ListNode node5 = new ListNode(5); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; this.head = node1; } @Override public void addFirst(int data) { ListNode node = new ListNode(data); node.next = head; head = node; } @Override public void addLast(int data) { ListNode node = new ListNode(data); if(head == null){ head = node; return; } ListNode cur = head; while(cur.next != null){ cur = cur.next; } cur.next = node; } @Override public void addIndex(int index, int data) { int len = this.size(); if(index > len || index < 0){ System.out.println("index位置不合法!!"); return; } if(index == 0){ addFirst(data); return; } if(index == len){ addLast(data); return; } ListNode node = new ListNode(data); ListNode cur = head; while (index - 1 != 0) { cur = cur.next; index--; } node.next = cur.next; cur.next = node; } @Override public boolean contains(int key) { ListNode cur = head; while(cur != null){ if( cur.val == key){ return true; } cur = cur.next; } return false; } @Override public void remove(int key) { ListNode cur = head; if(head == null){ return; } if(head.val == key){ head = head.next; return; } ListNode fr = this.findNodeOfKey(key); if(fr == null){ return; } ListNode re = fr.next; fr.next = re.next; } private ListNode findNodeOfKey(int key){ ListNode cur = head; while(cur.next != null){ if(cur.next.val == key){ return cur; } cur = cur.next; } return null; } @Override public void removeAllKey(int key) { if (head == null) { return; } while (head != null && head.val == key) { head = head.next; } if (head == null) { return; } ListNode cur = head; while (cur != null && cur.next != null) { if (cur.next.val == key) { // 跳过当前节点的下一个节点 cur.next = cur.next.next; } else { // 继续遍历 cur = cur.next; } } } @Override public int size() { ListNode cur = head; int len = 0; while(cur != null){ len++; cur = cur.next; } return len; } @Override public void clear() { ListNode cur = head; while(cur != null){ cur.next = null; cur = cur.next; } head = null; } @Override public void display() { ListNode cur = head; while( cur != null){ System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); }}test：
package demo;public class Test { public static void main(String[] args) { MySinglelist list = new MySinglelist(); list.addLast(1); list.addLast(2); list.addLast(3); list.addLast(4); list.addLast(5); list.display(); list.addFirst(99); list.display(); list.addIndex(6,78); list.display(); System.out.println(list.contains(3)); System.out.println(list.contains(78)); System.out.println(list.contains(96)); System.out.println(list.size()); list.remove(78); list.display(); list.remove(99); list.display(); list.addFirst(2); list.addLast(2); list.removeAllKey(2); list.display(); list.clear(); list.display(); }}运行结果：
1 2 3 4 5
99 1 2 3 4 5
99 1 2 3 4 5 78
true
true
false
7
99 1 2 3 4 5
1 2 3 4 5
1 3 4 5
题目：反转一个单链表。答题
思路：遍历链表一遍，将遍历到的节点依次移至head位置。
class Solution { public ListNode reverseList(ListNode head) { if (head == null) { return head; } ListNode cur = head.next; head.next = null; while (cur != null) { ListNode curN = cur.next; cur.next = head; head = cur; cur = curN; } return head; }}题目：给定一个带有头结点head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。答题思路：使用快慢指针，快指针一次走2步，慢指针一次走1步，当快指针走到最后的时候，慢指针指向的节点就是中间节点。
class Solution { public ListNode middleNode(ListNode head) { if(head == null){ return null; } ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; }}题目：输入一个链表，输出该链表中倒数第k个结点。 答题
思路：使用快慢指针，快指针先走k步，两指针再同时走，每次走一步，使两个指针之间永远隔着k个节点，当快指针走到最后的时候，慢指针指向的节点就是倒数第k个节点。
class Solution { public int kthToLast(ListNode head, int k) { ListNode fast = head; ListNode slow = head; while(k != 0){ fast = fast.next; k--; } while(fast != null){ fast = fast.next; slow = slow.next; } return slow.val; }}题目： 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 答题
思路：
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode newH = new ListNode(-1); ListNode tmp = newH; while (list1 != null && list2 != null) { if (list1.val < list2.val) { tmp.next = list1; list1 = list1.next; tmp = tmp.next; } else { tmp.next = list2; list2 = list2.next; tmp = tmp.next; } } if(list1 != null){ tmp.next = list1; } if(list2 != null){ tmp.next = list2; } return newH.next; }}题目：编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。答题
思路：
public class Partition { public ListNode partition(ListNode pHead, int x) { // write code here ListNode cur = pHead; ListNode bs = null; ListNode be = null; ListNode as = null; ListNode ae = null; while (cur != null) { if (cur.val < x) { //第一次插入 if (bs == null) { bs = be = cur; } else { be.next = cur; be = be.next; } } else { if (as == null) { as = ae = cur; } else { ae.next = cur; ae = ae.next; } } cur = cur.next; } if (bs == null) { return as; } be.next = as; if (as != null) { ae.next = null; } return bs; }}题目：链表的回文结构。 答题
思路：1.使用快慢指针定位中间节点；
2.翻转中间节点后面的节点顺序；
3.判断val。
class Solution { public boolean isPalindrome(ListNode head) { if (head == null) { return true; } // 1.使用快慢指针定位中间节点 ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } // 2.翻转中间节点后面的节点顺序 ListNode cur = slow.next; while (cur != null) { ListNode curN = cur.next; cur.next = slow; slow = cur; cur = curN; } // 3.判断val while (head != slow) { if (head.val != slow.val) { return false; } if (head.next == slow) { return true; } head = head.next; slow = slow.next; } return true; }}题目：输入两个链表，找出它们的第一个公共结点。 答题
思路：求两个链表长度的差值len，让较长链表的头结点指针先走len步，再让两指针同时走，相遇的节点就是第一个公共节点。
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA = 0; int lenB = 0; ListNode pl = headA; ListNode ps = headB; // 1.求两链表长度 while (pl != null) { lenA++; pl = pl.next; } while (ps != null) { lenB++; ps = ps.next; } pl = headA; ps = headB; // 2.求差值 int len = lenA - lenB; if (len < 0) { pl = headB; ps = headA; len = -len; } // 3.先让pl走len步 while (len != 0) { pl = pl.next; len--; } // 4.pl ps同时走直至相遇 while (pl != ps) { pl = pl.next; ps = ps.next; } return pl; }}题目：给定一个链表，判断链表中是否有环。答题
思路： 使用快慢指针，快指针一次走2步，慢指针一次走1步，速度相差1，如果有环，两指针总能相遇。
public class Solution { public boolean hasCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ return true; } } return false; }}题目：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回null（仅考虑fast比slow多走一圈的情况）。答题
思路：
public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ break; } } if(fast == null || fast.next == null){ return null; } slow = head; while(fast != slow){ fast = fast.next; slow = slow.next; } return slow; }}无头双向链表，也被称为双链表，是一种双向链接的线性数据结构，每个节点有两个指针，分别指向前一个节点和后一个节点。
与单向链表不同的是，无头双向链表在操作上更加灵活，因为每个节点都有指向前一个节点的指针。这意味着可以从头到尾或者从尾到头遍历链表，也可以在 O(1) 时间复杂度下进行节点的插入和删除操作。
（Ilist接口同无头单向非循环链表）
MyLinkedlist:
package demo;public class MyLinkedlist implements Ilist{ static class ListNode{ public int val; public ListNode prev; public ListNode next; public ListNode(int val) { this.val = val; } } public ListNode head; public ListNode last; @Override public void addFirst(int data) { ListNode node = new ListNode(data); if(head == null){ head = last = node; }else{ node.next = head; head.prev = node; head = node; } } @Override public void addLast(int data) { ListNode node = new ListNode(data); if(head == null){ head = last = node; }else{ node.prev = last; last.next = node; last = node; } } @Override public void addIndex(int index, int data) { int len = size(); if(index < 0 || index > len){ System.out.println("index位置不合法!"); } if(index == 0){ addFirst(data); return; } if(index == len){ addLast(data); return; } ListNode node = new ListNode(data); ListNode cur = head; while(index - 1 != 0){ cur = cur.next; index--; } ListNode curN = cur.next; cur.next = node; node.prev = cur; node.next = curN; curN.prev = node; } @Override public boolean contains(int key) { ListNode cur = head; while(cur != null){ if(cur.val == key){ return true; } cur = cur.next; } return false; } @Override public void remove(int key) { ListNode cur = head; while(cur != null){ //注意链表只有一个节点的情况!!! if(cur.val == key){ if(cur == head){ head = head.next; if(head != null) { head.prev = null; } }else if(cur == last){ last = last.prev; last.next = null; }else{ cur.prev.next = cur.next; cur.next.prev = cur.prev; } return; } cur = cur.next; } } @Override public void removeAllKey(int key) { ListNode cur = head; while(cur != null){ //注意链表只有一个节点的情况!!! if(cur.val == key){ if(cur == head){ head = head.next; if(head != null) { head.prev = null; } }else if(cur == last){ last = last.prev; last.next = null; }else{ cur.prev.next = cur.next; cur.next.prev = cur.prev; } } cur = cur.next; } } @Override public int size() { int len = 0; ListNode cur = head; while(cur != null){ len++; cur = cur.next; } return len; } @Override public void clear() { ListNode cur = head; while(cur != null){ ListNode curN = cur.next; cur.prev = null; cur.next = null; cur = curN; } head = last = null; } @Override public void display() { ListNode cur = head; while(cur != null){ System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); }}Test:
package demo;public class Test { public static void main(String[] args) { MyLinkedlist list = new MyLinkedlist(); list.addFirst(5); list.addFirst(4); list.addFirst(3); list.addFirst(2); list.addFirst(1); list.display(); list.addLast(99); list.display(); System.out.println(list.size()); System.out.println(list.contains(1)); System.out.println(list.contains(100)); list.addIndex(4,78); list.display(); list.remove(78); list.display(); list.addIndex(0,36); list.addIndex(3,36); list.display(); list.removeAllKey(36); list.display(); list.clear(); list.display(); }}运行结果：
1 2 3 4 5
1 2 3 4 5 99
6
true
false
1 2 3 4 78 5 99
1 2 3 4 5 99
36 1 2 36 3 4 5 99
1 2 3 4 5 99
LinkedList是一种常用的数据结构，实现了List接口和Deque接口，可以用于存储一系列的元素。它的特点是可以快速地在任意位置进行插入、删除和访问操作。
使用LinkedList可以按照以下步骤进行：
1.导入LinkedList类：在java代码中，首先需要导入LinkedList类，可以使用以下代码导入：
import java.util.LinkedList;2.创建LinkedList对象：创建一个空的LinkedList对象，可以使用以下代码创建：
LinkedList linkedList = new LinkedList<>(); 这里的Type表示你要存储的元素的类型，例如Integer、String等。
如：
public static void main(String[] args) { // 构造一个空的LinkedList List list1 = new LinkedList<>(); List list2 = new java.util.ArrayList<>(); list2.add("JavaSE"); list2.add("JavaWeb"); list2.add("JavaEE"); // 使用ArrayList构造LinkedList List list3 = new LinkedList<>(list2);} 方法 | 解释 |
boolean add(E e) | 尾插e |
void add(int index, E element) | 将e 插入到index 位置 |
boolean addAll(Collection 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 | 截取部分list |
fori遍历
foreach遍历
for (int e:list) { System.out.print(e + " ");}System.out.println()迭代器正向遍历
ListIterator it = list.listIterator();while(it.hasNext()){ System.out.print(it.next()+ " ");}System.out.println(); 迭代器反向遍历
ListIterator rit = list.listIterator(list.size());while (rit.hasPrevious()){ System.out.print(rit.previous() +" ");}System.out.println(); 不同点 | ArrayList | LinkedList |
存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
随机访问 | 支持O(1) | 不支持：O(N) |
头插 | 需要搬移元素，效率低O(N) | 只需修改引用的指向，时间复杂度为O(1) |
插入 | 空间不够时需要扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
在一个循环双向链表中，要在p所指的节点之前插入s所指节点，以下代码正确的执行次序是（ ）
① p.prev.next=s;
② p.prev=s;
③ s.prev=p.prev;
④ s.next=p;
A.④③①②
B.④③②①
C.②①④③
D.②①③④
答案：A
下列判断带头结点双向循环链表为空的语句中，正确的是（ ）
A.head == null;
B.head.next == null;
C.head.next == head;
D.head != null;
答案：C
