当前位置：首页 > news >正文

LinkedList与链表

news 2025/8/14 20:15:14

1. 链表

2. MySingleList链表的实现

3. 链表面试题

4. LinkedList双向链表的模拟实现

5. LinkedList的遍历

6. ArrayList和LinkedList的区别

1. 链表

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

链表结构有很多，我们重点掌握两种：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表...这种结构在笔试面试中出现很多无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表

2. MySingleList链表的实现

重点：使用 head=head.next ，但是有一个缺点：head的指向发生变化，可以ListNode cur=head;这样只需改变cur的指向即可。

display方法（输出链表）：

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

createList方法（创建一个链表）：

    public void createList() {ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(13);ListNode node3 = new ListNode(14);ListNode node4 = new ListNode(15);ListNode node5 = new ListNode(16);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;}

size方法（链表的长度）：

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

问题：while循环里面，可不可以是cur.next!=null;答：可以！只需初始化len=1即可。

contains方法（判断是否包含某个数）：

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

addFirst方法（头插法）：

重点是：node.next=head; head=node;即使node==null也可以

特殊情况：一个节点都没有：if(head==null)

    public void addFirst(ListNode node, int val) {if (head == null) {return;}node.next = head;node.val = val;head = node;}

addLast方法（尾插法）：

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

甚至可以通过头插和尾插创建链表！

addIndex方法（插入到指定位置）：

先判断index是否合法，不合法的话进行打印错误信息处理

重点是：node.next=cur.next;cur.next=node;

    public void addIndex(int index, ListNode node) {ListNode cur = head;if (index < 0 || index >= size()) return;while ((--index) != 0) {cur = cur.next;}node.next = cur.next;cur.next = node;}

问题：cur.next=node;node.next=cur.next;是否可以？答：不可以！

我想试着换一种方法，从头开始count++;直到等于index.

    //另一种方法：public void addIndex(int index, ListNode node) {ListNode cur = head;int count = 0;while ((++count) != index) {cur = cur.next;}node.next = cur.next;cur.next = node;//从后往前的顺序}

规律：所有的插入，优先绑定后边

remove方法（删除一个节点）：

首先判断是否为空；

如果要删的是头节点，那必须要在最开始的时候处理。

重点是：cur.next=del.next;或者cur.next=cur.next.next;

if(cur.next.val==key)真正要删除的节点是del=cur.next;

还要判断该链表是否包含要删除的节点。

    public void remove(int key) {if (head == null) {return;}if (head.val == key) {head = head.next;return;}ListNode cur = head;ListNode del = cur.next;while (cur.next != null) {if (cur.next.val == key) {cur.next = del.next;}cur = cur.next;del = del.next;}}

removeAllKey方法（删除所有等于key的节点）：

这里要定义两个节点：prev和cur，prev=head,cur=head.next;

同理，如果head.val==key,要head=head.next;但是，这句话只能执行一次，如果下一个还是key，将不会再执行这个if语句，所以要么将这个if改为while循环，要么将这个if放在该方法的最后（即，最后再处理head），执行完以后直接退出，且只针对于head.

    public void removeAllKey(int key) {if (head == null) {return;}ListNode prev = head;ListNode cur = head.next;while (cur != null) {while (cur.val == key) {prev.next = cur.next;cur = cur.next;}prev = cur;cur = cur.next;}if (head.val == key) {head = head.next;}}

clear方法（清空链表）：

直接将head置为空；也可以遍历置空。

    public void clear() {head = null;}

3. 链表面试题

203. 移除链表元素 - 力扣（LeetCode）——>与上面所写的代码逻辑一样

206. 反转链表 - 力扣（LeetCode）——>要求：只遍历一遍链表，在链表本身进行修改（巧妙使用头插法）注意：这道题很经典！！！

876. 链表的中间结点 - 力扣（LeetCode）——>要求：不能求链表的长度（不可以len/2）。可以定义两个指针，定义一个fast，一个flow。fast一次走2步，flow一次走1步，链表长度奇偶分开

面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）——>同样使用fast和flow，巧妙使用两指针之间的距离。拓展：不求链表的长度，将k的所有取值情况的返回结果写出。

21. 合并两个有序链表 - 力扣（LeetCode）

面试题 02.04. 分割链表 - 力扣（LeetCode）

面试题 02.06. 回文链表 - 力扣（LeetCode）——>要求：不能申请额外的内存

160. 相交链表 - 力扣（LeetCode）
141. 环形链表 - 力扣（LeetCode）

【扩展问题】

为什么快指针每次走两步，慢指针一次走一步？

假设链表带环，快指针先进环，慢指针后进环，最差情况是两个指针之间的距离刚好是环的长度。此时，指针每移动一次，之间的距离就缩小一步，因此，在慢指针走完一圈之前，快指针肯定可以与慢指针相遇。

快指针一次走3步，4步...n步可以吗？

会有错过的可能。

142. 环形链表 II - 力扣（LeetCode）——>画图分析思路

4. LinkedList双向链表的模拟实现

LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在任意位置插入或删除元素时，不需要搬移元素，效率较高。

头插法addFirst：

    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;}}

尾插法addLast:

    public void addLast(int data){ListNode node = new ListNode(data);if(head == null){head=last=node;}else{last.next=node;}}

坐标插法addIndex：

    public void addIndex(int index, int data) {int len = size();if (index < 0 || index > len) {return;}if (index == 0) {addFirst(data);return;}if (index == len - 1) {addLast(data);return;}ListNode node = new ListNode(data);ListNode cur = head;while (index != 0) {cur = cur.next;index--;}node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}

移除元素remove方法：

    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 {cur.prev.next = cur.next;if (cur.next == null) {//尾节点last = last.prev;} else {cur.next.prev = cur.prev;}}return;//}cur = cur.next;}}

移除所有等于该值的元素removeAllKey方法：

    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 {cur.prev.next = cur.next;if (cur.next == null) {//尾节点last = last.prev;} else {cur.next.prev = cur.prev;}}}cur = cur.next;}}

清除元素clear方法：

    public void clear() {ListNode cur = head;while (cur != null) {ListNode curN = cur.next;cur.next = null;cur.prev = null;cur = curN;}head = last = null;}

        List<Integer> linkedList1 = new LinkedList<>();linkedList1.add(1);linkedList1.add(2);linkedList1.add(3);LinkedList<Integer> linkedList2 = new LinkedList<>();linkedList2.addFirst(1);linkedList2.add(2);//默认尾插System.out.println(linkedList2);//[1, 2]linkedList2.addAll(linkedList1);System.out.println(linkedList2);//[1, 2, 1, 2, 3]

5. LinkedList的遍历

foreach遍历：

        //foreach遍历for (Integer i : linkedList2) {System.out.print(i + " ");//1 2 1 2 3}System.out.println();

使用迭代器遍历---正向遍历：

        //使用迭代器遍历---正向遍历Iterator<Integer> iterator = linkedList2.iterator();while (iterator.hasNext()) {System.out.print(iterator.next() + " ");//1 2 1 2 3}System.out.println();
//        正向遍历也可以这样写：
//        ListIterator<Integer> it = linkedList2.listIterator();
//        while(it.hasNext()){
//            System.out.print(it.next()+ " ");//1 2 1 2 3
//        }
//        System.out.println();

使用反向迭代器---反向遍历：

        //使用反向迭代器---反向遍历ListIterator<Integer> iterator1 = linkedList2.listIterator(linkedList2.size());while (iterator1.hasPrevious()) {System.out.print(iterator1.previous() + " ");//3 2 1 2 1 }System.out.println();