java 链表头插法和尾插法

1、链表概念

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

链表是由值和地址组成，地址指向下一个值的地址，如下图所示

image.png

我们先定义一个节点类Listnode，里面包含值和地址属性，再通过构造器传值为这个值在内存中申请一块区域。代码如下：

public class Listnode {
        //链表中一个节点的值属性
    public int value;
        //链表中一个节点的指针域属性，指向下一个值的地址，因为下一块区域是Listnode类型的所以next也是Listnode类型
    public Listnode next;
        //构造器，通过值传递给value赋值
    public Listnode(int n) {
        this.value=n;
    }
    
}

2.头插法

先创建一个链表类Linklist.

头插法的思路是定义一个头指针Listnode head=null，把第一个节点的地址通过值传递给它，再创建节点时，让这个新节点的next指针指向旧节点，再让这个头指针指向新节点。如下图：

image.png
image.png
image.png
image.png

头插法看如下代码：

public class LinkList {
    
    ListNode head = null;

    public void headInsert(int value) {
        //要插入的新节点
        ListNode newListNode = new ListNode(value);

        //如果第一次插入节点，此时head为null，直接将新节点赋值给head
        if (head == null) {
            head = newListNode;
            return;
        }
        //如果不是第一次插入节点
        //将新节点的next指向旧节点，因为旧节点通过值传递的方式传给head
        newListNode.next = head;
        //新节点通过值传递的方式传给head
        head = newListNode;
    }
}

3.尾插法

尾插法的思路是先定义一个游标temp，游标从头结点head开始，如果它的next指针域不是null，就让游标指向下一个，直到游标指向next指针域为null，然后在这个节点后插入新的节点。

image.png
image.png
image.png

尾插法代码如下：

public class LinkList {
    ListNode head = null;

    public void endInsert(int value) {
        //要插入的新节点
        ListNode newListNode = new ListNode(value);

        //判断头结点是否为空，空就通过值传递把新节点传给头节点，直接return不再走下面的流程
        if (head == null) {
            head = newListNode;
            return;
        }


        //定义游标temp
        ListNode temp = head;

        //通过游标判断此节点的next指针域是否为空，不是就指向下一个节点
        while(temp.next != null) {
            temp = temp.next;
        }

        //此时指向最后一个节点，让它的next指针域指向新节点
        temp.next = newListNode;
    }
}

4.获取单链表长度

代码如下：

public class LinkList {
  public int getNodeLength(ListNode head) {
        if (head == null) {
            return 0;
        }

        ListNode temp = head;
        int length = 0;
        while(temp != null) {
            length ++;
            temp = temp.next;
        }
        return length;
    } 
}

————————————————
参考：https://blog.csdn.net/m566666/article/details/121711252