Linked list is a non-contiguous storage structure in physical storage structure, and the logical order of data elements is realized through the order of reference links in the linked list.
The linked list is divided into whether it is the leader node, whether it has a ring, whether it is one-way or two-way
A one-way linked list without a leader and a ring: the highest appearance rate in the written test interview

Without the leading node, with the leading node, I drew a picture to illustrate

The purpose of the puppet node is to make it easier to write code.
About acyclic linked list and doubly linked list

There are several functions to be realized about the linked list (headless, one-way, non-circular)

// 1. Realization of headless one-way non-circular linked list
public class SingleLinkedList {
     //head insertion
     public void addFirst(int data);
     //tail plugging
     public void addLast(int data);
     //Insert at any position, the first data node is subscript 0
     public boolean addIndex(int index,int data);
     //Find whether the keyword key is included in the singly linked list
     public boolean contains(int key);
     //Delete the node whose keyword is key for the first time
     public void remove(int key);
     //Delete all nodes whose value is key
     public void removeAllKey(int key);
     //Get the length of the singly linked list
     public int size();
     public void display();
     public void clear();
 }

First of all, we need to use a class to represent the node. This node contains two parts, one part is the stored data and methods, and the other part is a reference to the next node.

class LinkNode{
    public int date;
    public LinkNode next = null;

    public LinkNode(int date){
        this.date = date;
    }
}

1. The first is the head plugging method

We need to judge two situations,
1. If the linked list is an empty linked list, head points to null at this time
2. If the current linked list is not empty, head is not null at this time

If it is the first case, just point the head reference to the newly inserted Node
If it is the second case, you need to consider the following operations

	private LinkNode head = null;//Create a head node, with this head node, you can get the next of the remaining elements

    public void addFirst(int elem){
        LinkNode node = new LinkNode(elem);
        if(this.head == null){
            //The case of an empty list
            this.head = node;
            return;
        }
        node.next = this.head;
        this.head = node;
        return;
    }

2. Print out the linked list for testing

Print all elements of a linked list:

    public void display(){
        System.out.print("[");
        for(LinkNode node = this.head; node != null; node = node.next){
            System.out.print(node.date);
            if(node.next!= null){
                System.out.print(",");
            }
        }
        System.out.println("]");
    }

3. Tail plug

1. If the linked list is an empty linked list, then just insert the node directly
2. If it is not empty, you need to find the last node, and point the next reference of the last node to node

    public void addLast(int elem){
        LinkNode node = new LinkNode(elem);
        if(this.head == null){
            this.head = node;
            return;
        }
        LinkNode cur = this.head;
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }

4. Get the length of the singly linked list

    public int size(){
        int size = 0;
        for(LinkNode node = this.head;
            node != null;node = node.next){
            size++;
        }
        return size;
    }

Insert at any position, the first data node is subscript 0

5.1 Validity check, index<0 or greater than len is illegal
Divided into three cases of head plug and tail plug, middle plug
The analysis of interpolation is as follows. To insert index, you need to find index-1;

	public void addIndex(int index , int elem){
        LinkNode node = new LinkNode(elem);
        int len = size();
        if(index < 0 || index > len){
            //illegal
            return;
        }
        //plug
        if(index == 0){
            addFirst(elem);
            return;
        }
        //tail plug
        if(index == len){
            addLast(elem);
            return;
        }
        LinkNode prev = getIndexPos(index - 1);
        node.next = prev.next;
        prev.next = node;
    }

getIndexPos

public LinkNode getIndexPos(int index){
        LinkNode cur = this.head;
        for (int i = 0;i < index;i++){
            cur = cur.next;
        }
        return cur;
    }

6. Find whether the keyword key is included in the singly linked list

    public boolean contains(int toFind) {
        // Traverse the linked list directly and compare each element in turn
        for (LinkedNode cur = this.head;
                cur != null; cur = cur.next) {
            if (cur.data == toFind) {
                return true;
            }
        }
        return false;
    }

7. Delete the node whose keyword is key for the first time

There are three situations to consider
1. The case of an empty linked list
2. Deleted time header node

3. Delete the intermediate node (it is important to find the previous node)

    public void romove(int toremove){
        //empty list
        if (this.head == null) {
            return;
        }
        //delete head node
        if(this.head.date == toremove){
            this.head = this.head.next;
            return;
        }
        //Delete in the middle
        LinkNode prev = searchPrev(toremove);
        prev.next = prev.next.next;
    }
    public LinkNode searchPrev(int toremove){
        //Find the previous position of the deleted element
        for(LinkNode cur = this.head; cur != null;cur = cur.next){
            if(cur.next.date == toremove){
                return cur;
            }
        }
        return null;
    }

delete all key s

public void romoveAllKey(int toremove){
        if(this.head == null){
            return;
        }
        for(LinkNode cur = this.head;cur != null;
            cur = cur.next){
            if(cur.date == toremove){
                romove(toremove);
            }
        }
    }

test code

public class Test {
    public static void main(String[] args){
        testAddFirst();
        testAddLast();
        testAddIndex();
        testremove();
        testRemoveAllKey();
    }
    public static void testAddFirst(){
        System.out.println("test addfirst method");
        LinkedList linkedList = new LinkedList();
        linkedList.addFirst(1);
        linkedList.addFirst(2);
        linkedList.addFirst(3);
        linkedList.addFirst(4);
        linkedList.display();
    }
    public static void testAddLast(){
        System.out.println("test addLast method");
        LinkedList linkedList = new LinkedList();
        linkedList.addLast(1);
        linkedList.addLast(2);
        linkedList.addLast(3);
        linkedList.display();
    }
    public static void testAddIndex(){
        System.out.println("test addIndex method");
        LinkedList linkedList = new LinkedList();
        linkedList.addFirst(1);
        linkedList.addFirst(2);
        linkedList.addLast(2);
        linkedList.addLast(3);
        linkedList.addIndex(4,5);
        linkedList.display();
        System.out.println(linkedList.contains(10));
    }
    public static void testremove(){
        System.out.println("test remove");
        LinkedList linkedList = new LinkedList();
        linkedList.addFirst(1);
        linkedList.addFirst(2);
        linkedList.addLast(2);
        linkedList.addLast(3);
        linkedList.addIndex(2,5);
        linkedList.romove(5);
        linkedList.display();
    }
    public static void testRemoveAllKey(){
        System.out.println("test removeallKesy");
        LinkedList linkedList = new LinkedList();
        linkedList.addFirst(1);
        linkedList.addFirst(1);
        linkedList.addLast(1);
        linkedList.addLast(1);
        linkedList.addIndex(2,1);
        linkedList.display();
        linkedList.romoveAllKey(1);
        linkedList.display();
    }
}

Linked list code

class LinkNode{
    public int date;
    public LinkNode next = null;

    public LinkNode(int date){
        this.date = date;
    }
}
public class LinkedList{
    private LinkNode head = null;//Create a head node, with this head node, you can get the next of the remaining elements

    public void addFirst(int elem){
        LinkNode node = new LinkNode(elem);
        if(this.head == null){
            //The case of an empty list
            this.head = node;
            return;
        }
        node.next = this.head;
        this.head = node;
        return;
    }
    public void addLast(int elem){
        LinkNode node = new LinkNode(elem);
        if(this.head == null){
            this.head = node;
            return;
        }
        LinkNode cur = this.head;
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }
    public void display(){
        System.out.print("[");
        for(LinkNode node = this.head; node != null; node = node.next){
            System.out.print(node.date);
            if(node.next!= null){
                System.out.print(",");
            }
        }
        System.out.println("]");
    }
    public void addIndex(int index , int elem){
        LinkNode node = new LinkNode(elem);
        int len = size();
        if(index < 0 || index > len){
            //illegal
            return;
        }
        //plug
        if(index == 0){
            addFirst(elem);
            return;
        }
        //tail plug
        if(index == len){
            addLast(elem);
            return;
        }
        LinkNode prev = getIndexPos(index - 1);
        node.next = prev.next;
        prev.next = node;
    }
    public LinkNode getIndexPos(int index){
        LinkNode cur = this.head;
        for (int i = 0;i < index;i++){
            cur = cur.next;
        }
        return cur;
    }
    public int size(){
        int size = 0;
        for(LinkNode node = this.head;
            node != null;node = node.next){
            size++;
        }
        return size;
    }
    public boolean contains(int key){
        for(LinkNode cur = this.head; cur != null;
            cur = cur.next){
            if(cur.date == key){
                return true;
            }
        }
        return false;
    }
    public void romove(int toremove){
        //empty list
        if (this.head == null) {
            return;
        }
        //delete head node
        if(this.head.date == toremove){
            this.head = this.head.next;
            return;
        }
        //Delete in the middle
        LinkNode prev = searchPrev(toremove);
//        prev.next = prev.next.next;
        LinkNode nodeToremove = prev.next;
        prev.next = nodeToremove.next;
    }
    public LinkNode searchPrev(int toremove){
        //Find the previous position of the deleted element
        for(LinkNode cur = this.head; cur != null;cur = cur.next){
            if(cur.next.date == toremove){
                return cur;
            }
        }
        return null;
    }
    public void romoveAllKey(int toremove){
        if(this.head == null){
            return;
        }
        for(LinkNode cur = this.head;cur != null;
            cur = cur.next){
            if(cur.date == toremove){
                romove(toremove);
            }
        }
    }
}