I hope to communicate with you and learn from each other through my blog. If you have any mistakes, please correct them in the comment area

1, What is a linked list

Sequential tables have defects in space utilization, system consumption and insertion elements. Linked list is the most commonly used dynamic storage method, which overcomes the shortcomings of sequential list.

Linked list is a non continuous and non sequential storage structure on the physical storage unit. The logical order of data elements is realized through the reference link order in the linked list

The linked list consists of a series of nodes (each element in the linked list is called a node), which can be generated dynamically at run time. Each node consists of two parts: one is to store the data field of the data element, and the other is to store the reference field pointing to the next node

There are many linked list structures, including the following 6 cases and 8 combinations

• Headless, headless
• Unidirectional and bidirectional
• Cyclic and non cyclic

In these eight cases, we generally focus on two of them, headless one-way acyclic list and headless two-way acyclic list

2, Hand torn list

The headless one-way acyclic linked list is implemented here

Attribute definition

We need to have linked list nodes and linked list objects, as follows:

Node object

public class Node {
    public int data;
    public Node next;
}

Construction method

public Node(int data) {
	this.data = data;    // Note that this should be used. If data is written directly in it, it is the formal parameter data
	this.next = null;
}

Linked list object

public class MyLinkedList {
    public Node head;
}

Construction method

public MyLinkedList() {
    this.head = null;
}

Implementation of linked list

//Head insert
public void addFirst(int data);
//Tail insertion
public void addLast(int data);
//Insert at any position, and the first data node is subscript 0
public void addIndex(int index,int data);
//Find whether the keyword key is included
public boolean contains(int key);
//Delete the node whose keyword is key for the first time
public void remove(int key);
//Delete all nodes with the value of key
public void removeAllKey(int key);
//Get the length of the single linked list
public int size();
public void display();
public void clear();

Note: when implementing these methods, pay attention to traversing the linked list while loop. The judgment condition should be cur next != Null or cur= null

When inserting or deleting elements, consider boundary conditions and special cases (only one node, empty node, etc.)

Head insert

public void addFirst(int data) {
    Node newNode = new Node(data);
    if (this.head == null) {     // When it is an empty linked list, you only need to make the head point to the node
        head = newNode;        
        return;
    }
    newNode.next = head;
    head = newNode;
}

Tail insertion

Pay attention to special treatment when the linked list is empty If it is not empty, find the tail by traversing the linked list, and then insert it

public void addLast(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        return;
    }
    Node cur = head;
    while (cur.next != null) {
        cur = cur.next;
    }
    cur.next = newNode;
}

Get the length of the single linked list

public int size() {
    int count = 0;
    Node cur = this.head;
    while (cur != null) {
        cur = cur.next;
        count++;
    }
    return count;
}

Insert anywhere

Set the first data node as subscript 0. Note that there will be header insertion, tail insertion, illegal subscript, etc

public void addIndex(int index, int data) {
    if (index < 0 || index > this.size()) {
        throw new RuntimeException("index" + ":" + index);
    }
    Node newNode = new Node(data);
    if (index == 0) {    // Head insert
        this.addFirst(data);
        return;
    }
    if (index == this.size()) {   // Tail insertion
        this.addLast(data);
        return;
    }
    Node cur = this.head;
    while (index - 1 != 0) {
        cur = cur.next;
        index--;
    }
    newNode.next = cur.next;
    cur.next = newNode;
}

Find whether the keyword key is included

Traverse the linked list and compare the node data with the key

public boolean contains(int key) {
    Node cur = this.head;
    while (cur != null) {
        if (cur.data == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

Delete the node whose keyword is key for the first time

Traverse the linked list, find the first node with key and delete it. Special cases such as empty linked list and header deletion should be considered

public void remove(int key) {
    if (this.head == null) {
        return;
    }
    if (head.data == key) {   // Header deletion
        head = head.next;
        return;
    }
    Node cur = this.head;
    while (cur.next != null) {
        if (cur.next.data == key) {
            break;
        }
        cur = cur.next;
    }
    if (cur.next != null) {
        cur.next = cur.next.next;
    }
}

Print single linked list

public void display() {
    Node cur = this.head;
    while (cur != null) {
        System.out.print(cur.data + "->");
        cur = cur.next;
    }
    System.out.print("null");
}

Empty linked list

After using the linked list, use the clear() method to prevent memory leakage (check the process number jps, redirect jmap - histo: Live 6666 > e: \ Niubi. Txt)

public void clear() {
    this.head = null;
}

Delete all nodes with the value of key

Note: 1 When does prev jump back? The first node should not be judged at the beginning, but the first node should be judged after all the subsequent nodes are deleted

public void removeAll(int key) {
    if (this.head == null) {
        return;
    }
    Node prev = this.head;
    Node cur = this.head.next;
    while (cur != null) {
        if (cur.data == key) {
            prev.next = cur.next;
            cur = cur.next;
        } else {
            prev = cur;
            cur = cur.next;      // Not key, cur and prev jump back
        }
    }
    if (this.head.data == key) {
        this.head = this.head.next;
    }
}

2. Two way linked list

Here, take the bidirectional headless acyclic linked list as an example, as shown in the following figure:

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-4bvzi6qi-1641391981418) (C: \ users \ lycre \ appdata \ roaming \ typora \ typora user images \ image-20220105182248704. PNG)]

Attribute definition

The node object and construction method are the same as that of single line table

Linked list object

The linked list object has one more tail attribute, which points to the tail node of the linked list

public class MyLinkedList{
    public Node head;
    public Node tail;
}

Construction method

Nonparametric construction method

public MyLinkedList() {
    this.head = null;
    this.tail = null;
}

Implementation of linked list

//Head insertion
public void addFirst(int data);
//Tail interpolation
public void addLast(int data);
//Insert at any position, and the first data node is subscript 0
public void addIndex(int index,int data);
//Find whether the keyword key is included
public boolean contains(int key);
//Delete the node whose keyword is key for the first time
public void remove(int key);
//Delete all nodes with the value of key
public void removeAllKey(int key);
//Get the length of the linked list
public int size();
//Print linked list
public void display();
//Clear the linked list and free up memory
public void clear();

Head insert

Pay attention to the empty linked list in the process of header insertion

public void addFirst(int data) {
    Node newNode = new Node(data);
    if (this.head == null) {    // When the linked list is empty
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
    }
}

Tail insertion

public void addLast(int data) {
    Node newNode = new Node(data);
    if (this.head == null) {   // The linked list is empty
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.prev = tail;
        this.tail.next = newNode;
        this.tail = newNode;
    }
}

Get the length of the linked list

public int size() {
    int count = 0;
    Node cur = this.head;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}

Insert anywhere

There are many situations to consider when inserting elements at any position. We should list all possible situations before writing to avoid ignoring some situations

Pay attention to judge the validity of index

public void addIndex(int index,int data) {
    if (index < 0 || index > this.size()) {
        throw new RuntimeException("index : "  + index);
    }
    Node newNode = new Node(data);
    if (index == 0) {
        if (this.head == null) {   // Head insert
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head.prev = newNode;
            this.head = newNode;
        }
    } else if (index == this.size()) {   // Tail insertion
        newNode.prev = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
    } else {
        Node cur = this.head;
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        Node prevNode = cur.prev;
        newNode.next = cur;
        newNode.prev = prevNode;
        prevNode.next = newNode;
        cur.prev = newNode;
    }
}

Find whether the keyword key is included

Directly traverse the linked list and compare them one by one

public boolean contains(int key) {
    Node cur = this.head;
    while (cur != null) {
        if (cur.data == key) {
            return true;
        }
    }
    return false;
}

Delete the node whose keyword is key for the first time

It involves head deletion, tail deletion, empty linked list, etc

public void remove(int key) {
    if (this.head == null) {
        return;
    }
    Node cur = this.head;
    while (cur != null) {        // Find the first node with key
        if (cur.data == key) {
            break;
        }
        cur = cur.next;
    } 
    if (cur == null) {
        return;          //No, go straight back
    }
    if (cur == this.head) {       // Header deletion
        this.head = head.next;
        this.head.prev = null;  
        return;
    }
    if (cur == this.tail) {     // Tail deletion
        cur.prev.next = null;
        this.tail = cur.prev;
        return;
    }
    Node prevNode = cur.prev;
    Node nextNode = cur.next;
    prevNode.next = nextNode;
    nextNode.prev = prevNode;
}

Delete all nodes with the value of key

public void removeAllKey(int key) {
    if (this.head == null) {
        return;
    }
    Node prevNode = this.head;
    Node cur = this.head.next;
    while (cur != null) {
        if (cur.data == key) {
            prevNode.next = cur.next;
            cur = cur.next;
            if (cur == null) {
                this.tail = prevNode;     // The last node value is key
            } else {
                cur.prev = prevNode;
            }
        } else {
            cur = cur.next;
            prevNode = prevNode.next;
        }
    }
    if (this.head.data == key) {
        this.head = this.head.next;
        if (this.head == null) {
            this.tail = null;      // Note that when all elements in the linked list are key s, not only the head but also the tail should be determined at the end
            return;
        }
        this.head.prev = null;
    }
}

Print linked list

public void display() {
    Node cur = this.head;
    while (cur != null) {
        System.out.print(cur.data + "->");
        cur = cur.next;
    }
    System.out.print("null");
}

Clear the linked list and free up memory

public void clear() {
    if (this.head == null) {
        return;
    }
    Node cur = this.head;
    Node nextNode;
    while (cur != null) {
        nextNode = cur.next;
        cur.prev = null;
        cur.next = null;
        cur = nextNode;
    }
    this.tail = null;
}

Note that there is a big difference between emptying a two-way linked list and a one-way linked list. You can't directly set the head to null, because the later nodes also save the references of the previous nodes, so we should empty the next field and prev field of all nodes

Welcome to pay attention!!!

Learn and communicate together!!!

Let's finish the programming!!!

--------------It's not easy to organize. Please support the third company------------------