The simplest dynamic data structure - linked list

What is a linked list?

In the last few articles, dynamic array, stack and queue are introduced respectively, which are all dynamically expanded through resize method, thus realizing dynamic data structure, but this method is called pseudo dynamic. The real dynamic data structure should start from the linked list. The linked list is the real dynamic data structure. A dynamic data structure does not need to deal with the fixed capacity problem, and it is the simplest dynamic data structure. It is very important to learn the linked list well, which is a foreshadowing for the complex data structure behind. The list of links is known by its name. Elements and elements are tied like chains. Elements can also be nodes. Whatever they are called, it's OK to understand them anyway. Each element consists of two parts, one is the element itself, and the other is a reference to the next element. Next, the element itself is called e, and its next reference is called next.

class Node<E>
{
    E e; //Current element itself
    Node next; //Reference to next element
}


The figure above shows that the e of the first element is 1, and its next is 2. The e of the second element is 2, and its next is 3. The e of the last element is 3, but the next is null, because 3 is the last element. It can be said that if the next of an element is null, it means that it is the last element. If I want to find 2, I'll find it through 1. If I want to find 3, I'm sorry. You have to find it through 1, because there is no direct relationship between 1 and 3. You can only find 2 through 1 first. 2 has the address of storage 3 in it. This also means that the linked list does not have the ability of random access. For example, the array can be found by index, which is very efficient. If the linked list wants to find an element, it can only traverse from the beginning to the end, and the query efficiency is low.

The realization of linked list

First, a Node internal class is created to be used only for LinkedList external classes. External classes cannot operate Node objects, which is safer. The member variables are e and Node next respectively. E is used to store the element itself, and next stores the reference of the next element. Two variables are maintained in LinkedList, Node head and size. Head is used to store the head elements of the current linked list, and size is used to maintain the number of elements in the linked list.

public class LinkedList<E> {
    //Internal maintenance of a Node object for external classes (LinkedList)
    private class Node<E> {
        public E e; //The element value of the current Node object
        public Node next; //Reference to the next object of the current Node object
        public Node(E e,Node next) {
            this.e = e;
            this.next = next;
        }
        public Node(E e) {
            this.e = e;
            this.next = null;
        }
        public Node() {
            this.e = null;
            this.next = null;
        }
    }

    //Head element node
    private Node head;
        //Current number of linked list nodes
    private int size;
    public LinkedList() {
        head = null;
        size = 0;
    }
    public int getSize() {
        return size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
}

Add a header node

Adding a head Node is to create a new Node. The e of the new Node is 666. The next of the new Node points to the original head Node. After changing the direction, maintain the head to make the newly created Node become the head Node. Finally, maintain the number of size s.

public void addFirst(E e)
{
    Node node = new Node(e); //Create a node
    node.next = head; //next of node is current header node
    head = node; //Change the head direction. Now the head position has become the latest node
    //head = new Node(e,head); the above three steps can be simplified into this writing method
    size++;
}

Add elements by index location

Now add the new element to the specified location, such as inserting a new element at the location with index 2. Then we need to find the element before index 2. After the new element is inserted, we need to maintain the pointing relationship. It used to be that the next of 1 is 2, now the next of 666 is 2, and the next of 1 is 666. After finding 1, first give the next of 1 to 666, let the next of 666 point to 2, and then the next of 1 point to 666. Look at the picture below or draw it by yourself. But how can I find the element with index 1? Traversal! We can maintain a variable to hold the value of each next. We can see that the location from the beginning element to 1 only needs next once.

public void addByIndex(E e,int index) //index = 2
{
    if(index < 0 || index > size)
        throw new IllegalArgumentException("Add failed. Because index is illegal.");
    if(index == 0)
        addFirst(e);
    //1. To get the element of a certain location, you need to look back from the first, because the first stores the second "contact information" and the second stores the third "contact information".
    //Here, the loop is just how many times to traverse to get the element before the index, and the X variable in it has no significance. You can also write x = 1; x < index; as long as the number of cycles is right.
    //0 1 2 3, if index = 2, then the element to be inserted is 0 1 〝 2 3, then traverse from the beginning of the element to get the node with index 1, only need to go through next once
    Node prevNode = head;
    for(int x = 0; x < index - 1; x++) {
        head = prevNode.next;
    }
    //2. After getting currentNode, maintain the pointing relationship
    Node node = new Node(e);
    node.next = prevNode.next;
    prevNode.next = node;
    //currentNode.next = new Node(node,currentNode.next); / / short form
    size++;
}

Introduction of virtual node

When implementing the addByIndex method above, you need to make a special judgment when the index is 0. Can we change an idea without special judgment so that addFirst method can also be reused? This is done by using virtual nodes. Design a dummyHead. Every time you add elements at the 0 th position, you can find the original head element position through dummyHead. Then the logic added by index can be reused.

private Node dummyHead;
private int size;
public LinkedList() {
    dummyHead = new Node(null, null); //Create virtual node
    size = 0;
}
//Add elements to linked list head
public void addFirst(E e) {
    addByIndex(e, 0);
}
//Add elements at the end of the list
public void addLast(E e) {
    addByIndex(e, size);
}
public void addByIndex(E e, int index) //3
{
    if (index < 0 || index > size)
        throw new IllegalArgumentException("Add failed. Because index is illegal.");
    //If the index is 3, there will be three times of next from dummyHead to index 2. The cycle starts from 0 and then < 3, that is, 0 1 2, three times in total
    Node currentNode = dummyHead; //Traverse dummy 0 1 2 -- 3 from scratch
    for (int x = 0; x < index; x++) {
        dummyHead = currentNode.next;
    }
    Node node = new Node(e);
    node.next = currentNode.next;
    currentNode.next = node;
    //currentNode.next = new Node(node,currentNode.next); / / short form
    size++;
}

It provides some basic methods, such as querying, deleting, whether to include an element, and modifying an element. As long as you master the idea of traversing the list, you can never leave it alone. It is important to control the index boundary.

public E get(int index) {
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Get filed.Index is not true!");
    Node currentNode = dummyHead;
    for (int x = 0; x < index; x++) {
        currentNode = currentNode.next;
    }
    return (E) currentNode.next.e;
}

public E getFirst()
{
    return get(0);
}

public E getLast()
{
    return get(size - 1);
}

public void set(E e,int index)
{
    if (index < 0 || index >= size)
        throw new IllegalArgumentException("Get filed.Index is not true!");
    Node currentNode = dummyHead;
    for(int x = 0; x < index; x++) {
        currentNode = currentNode.next;
    }
    currentNode.next.e = e;
}

public boolean contains(E e)
{
    Node currentNode = dummyHead;
    for(int x = 0; x < size; x++)
    {
        currentNode = currentNode.next;
        if(currentNode.e.equals(e))
        {
            return true;
        }
    }
    return false;
}

@Override
public String toString() {
    StringBuffer sb = new StringBuffer();
    sb.append("linkedHead[");
    Node currentNode = dummyHead;
    for(int x = 1; x <= size; x++)
    {
        currentNode = currentNode.next;
        sb.append(currentNode.e + "....");
    }
    sb.append("]linkedFooter");
    return sb.toString();
}

Delete operation

//Delete an element in a linked list
public E delete(int index)
{
    Node currentNode = dummyHead;
    for(int x = 0; x < index; x++) {
        currentNode = currentNode.next;
    }
    
    Node delNode = currentNode.next;
    currentNode.next = delNode.next;
    delNode.next = null;
    size--;
    return (E) delNode.e;
}

Tags: Java

Posted on Tue, 05 Nov 2019 04:10:17 -0800 by johnska7