链表

一.链表的介绍

1.什么是链表

链表:

  • 链表(linked list)是一种在物理上非连续、非顺序的数据结构,由若干节点(node)所组成
  • 单向链表的每一个节点又包含两部分,一部分是存放数据的变量data,另一部
    分是指向下一个节点的指针next。

image-20230830072140272

其中head为头指针,可以理解为当前指向或者遍历到的元素

内存中的图解

我们知道JVM里有栈区和堆区,栈区主要存引用,也就是一个指向实际对象的地址,而堆区存的才是创建的对象

假设我们栈中存放头结点,course,

image (2)

2.链表的定义

根据面向对象的理论,在Java里规范的链表应该这么定义:

public class ListNode {
    private int data; //存放数据
    private ListNode next; //存放下一个元素
    public ListNode(int data) {
        this.data = data; 
    }
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public ListNode getNext() {
        return next;
    }
    public void setNext(ListNode next) {
        this.next = next;
    }
}

但是在LeetCode中算法题中经常使用这样的方式来创建链表

public class ListNode {
    public int val;
    public ListNode next;

    ListNode(int x) {
        val = x;
        //这个一般作用不大,写了会更加规范,因为默认值是null
        next = null;
    }
}
ListNode listnode=new ListNode(1); //创建第一个节点,有没有都可以

这种是将属性公开,可以直接使用 listnode.vallistnode.next 来获取和修改值。但是,这也意味着数据的控制权降低,无法限制外部代码直接修改字段

3.链表遍历的两种方法

while
 while (Node != null) {
            System.out.println(currentWhile.data);
            currentWhile = currentWhile.next;
        }

当遍历到最后一个元素停止的话,循环使用currentWhile.next != null即可

for
for (int i = 0; i < 5; i++) {  // 假设链表长度为5
            System.out.println(currentFor.data);
            currentFor = currentFor.next;
        }

二.链表的增删改查

1.链表的遍历

可以知道链表的特性是链表最后一个元素的next是null,因此while循环条件是当当前指针指向元素的next

head:当谈论链表的 "head" 时,通常指的是链表的起始节点,具有数据和指针。在一些情况下,也可以将 "head" 视为一个指针,指向链表的第一个节点。这种指针的存在使得我们可以遍历整个链表,通过不断跟随 next 指针来访问每个节点。

public static int getListLength(Node head) {
int length = 0;
Node node = head; //头
while (node != null) {
    length++; //在需要将长度计数放在指针迭代前,否则会忽略第一个最初头结点的长度
    node = node.next; //指针指向下一个元素
}
return length; //返回链表长度
}

2.链表插入

单链表的插入,和数组的插入一样,过程不复杂,但是在编码时会发现处处是坑。单链表的插入操作需要要考虑三种情况:首部、中部和尾部。

(1)首部

链表表头插入新结点非常简单,容易出错的是经常会忘了head需要重新指向表头。 我们创建一个新结点newNode,怎么连接到原来的链表上呢?执行newNode.next=head即可。之后我们要遍历新链表就要从newNode开始一路next向下了是吧,但是我们还是习惯让head来表示,所以让head=newNode就行了,如下图:

image (3)

(2)在链表中间插入

在中间位置插入,我们必须先遍历找到要插入的位置,然后将当前位置接入到前驱结点和后继结点之间,但是到了该位置之后我们却不能获得前驱结点了,也就无法将结点接入进来了。这就好比一边过河一边拆桥,结果自己也回不去了。
为此,我们要在目标结点的前一个位置停下来,也就是使用cur.next的值而不是cur的值来判断,这是链表最常用的策略

例如下图中,如果要在7的前面插入,当cur.next=node(7)了就应该停下来,此时cur.val=15。然后需要给newNode前后接两根线,此时只能先让new.next=node(15).next(图中虚线),然后node(15).next=new,而且顺序还不能错。

答:由于每个节点都只有一个next,因此执行了node(15).next=new之后,结点15和7之间的连线就自动断开了,

从内存角度来分析就是:

节点 7 实际上已经从链表中移除了。然而,垃圾回收器会注意到现在没有任何变量或引用指向节点 7,这意味着节点 7 以后已经成为了不可达的对象,可以被垃圾回收。垃圾回收器会定期扫描内存,找到这些不可达的对象并释放它们占用的内存空间。这样,内存中就会有更多可用的空间来存储新的对象,从而防止内存溢出和提高程序的性能。如图:

image (4)

(3)在单链表的结尾插入结点

表尾插入就比较容易了,我们只要将尾结点指向新结点就行了

image (5)

示例

这里注意一点细节是,中间节点的插入和末尾节点的插入可以考虑为一种情况:

因为当添加的位置是最后一个时,nodeInsert.next = pNode.next;此时右边等于NULL,新加的节点的next刚好被赋值为NULL,可以简化步骤

/**
     * 链表插入
     * @param head       链表头节点
     * @param nodeInsert 待插入节点
     * @param position   待插入位置,从1开始
     * @return 插入后得到的链表头节点
     */
public static Node insertNode(Node head, Node nodeInsert, int position) {
    if (head == null) {
        //这里可以认为待插入的结点就是链表的头结点,也可以抛出不能插入的异常
        return nodeInsert;
    }
    //已经存放的元素个数
    int size = getLength(head); //遍历求出元素的个数
    if (position > size+1  || position < 1) {
        System.out.println("位置参数越界");
        return head;
    }

    //表头插入
    if (position == 1) {
        nodeInsert.next = head;
        // 这里可以直接 return nodeInsert;还可以这么写:
        head = nodeInsert;
        return head;
    }

    Node pNode = head;
    int count = 1;
    //这里position被上面的size被限制住了,不用考虑pNode=null
    while (count < position - 1) {
        pNode = pNode.next; 
        count++;
    }  
    //此时的PNode是添加的节点的前一个节点
    nodeInsert.next = pNode.next;
    pNode.next = nodeInsert;

    return head;
}

3.链表的删除

删除之前,需要说明的是有的删除节点还需要将删除的元素的next先置设置为null以后再删除,这步操作可以有,两者都可以达到效果,至少在堆中回收的时间不一样,但是最终都会被回收

删除同样分为在删除头部元素,删除中间元素和删除尾部元素。

(1)删除表头结点

一般只要执行head=head.next就行了。如下图,将head向前移动一次之后,原来的结点不可达,会被JVM回收掉。

image

(2)删除最后一个结点

找到要删除的结点的前驱结点,这里同样要在提前一个位置判断,例如下图中删除40,其前驱结点为7。遍历的时候需要判断cur.next是否为40,如果是,则只要执行cur.next=null即可,此时结点40变得不可达,最终会被JVM回收掉。

image (6)

(3)删除中间结点

删除中间结点时,也会要用cur.next来比较,找到位置后,将cur.next指针的值更新为cur.next.next就可以解决,如下图所示:

image (7)

实现

/**
     * 删除节点
     * @param head     链表头节点
     * @param position 删除节点位置,取值从1开始
     * @return 删除后的链表头节点
     */
public static Node deleteNode(Node head, int position) {
    if (head == null) {
        return null;
    }
    int size = getListLength(head);
    //思考一下,这里为什么是size,而不是size+1
    if (position > size || position <1) {
        System.out.println("输入的参数有误");
        return head;
    }
    if (position == 1) {
        //curNode就是链表的新head
        return head.next;
    } else {
        Node cur = head;
        int count = 1;
        while (count < position - 1) {
            cur = cur.next;
            count++;
        }
        Node curNode = cur.next;
        cur.next = curNode.next;
        //上面两行可以直接简化成:cur.next=cur.next.next
    }
    return head;
}