Simple implementation of linked list in Java

catalogue

1, Simple understanding of linked list

1. What does the linked list look like?

2. What is the node?

2, Code implementation of linked list

1. Construction of nodes

2. Construction of linked list

 3. View linked list length

4. Find whether to specify whether the element is in the single linked list

5. Insert an element at the specified position in the linked list

(1) . tail insertion

(2) head insertion

(3) middle insertion

6. Delete the first occurrence of the specified element in the linked list

(1) . tail deletion

(2) header deletion

(3) intermediate deletion

7. Printing of linked list

(1) Print the whole linked list

(2) print the linked list from the given position

8. Empty linked list

3, Summary

1, Simple understanding of linked list

In my last article, I explained the sequence list in detail. We can know that the sequence list is stored sequentially in memory, but the linked list we will explain in this article is just the opposite. The linked list is stored randomly in memory, which also shows that the linked list is very flexible. It can make rational use of a lot of space, and can realize their own connection through some "secret signals".

1. What does the linked list look like?

The linked list is composed of nodes, which are connected one by one like the train carriage, as shown in the figure below

2. What is the node?

The linked list is composed of one node. As shown in the figure below, the storage of each data in the linked list is composed of the following two parts:

  1. The area of the data element itself is called the data field;
  2. The area where the pointer to the direct successor element is located is called the pointer field;

Our linked list is linked by nodes. According to the above figure, it is not difficult to find that a node has two essential parts, one to store data and the other to store the address of the next node. Through the above understanding, we almost have a preliminary understanding of the linked list. Next, we start to build our own linked list with code.

2, Code implementation of linked list

1. Construction of nodes

The construction of a linked list is inseparable from the composition of nodes, so the first step of building a linked list is of course to lay the foundation and establish nodes. We can create a class to realize the creation of a node, and then assign a value to the node through the assignment of the construction method. Of course, this reference must be the reference of this node type, because our linked list is basically realized by pointing to the next node through the node

class NodeList{
    public int date;
    public NodeList next;
    public NodeList(int num){
        this.date = num;
    }
}

2. Construction of linked list

With a node, we can build a linked list. First, a linked list must have a head node. If there is no head node, there will be no leader, and all the linked list data will be lost. Therefore, this head node is very important, and then initialize the linked list. In fact, it is not different from the construction of nodes. I also use a construction method to define the beginning of a linked list, But the construction method of the node is to assign a value to the node, and the linked list initialization is to build a node and assign a value to it.

 public NodeList head;
    public MyLinkedList(int num){
            this.head  = new NodeList(num);
 }

 3. View linked list length

To find the length of the linked list, we need to build a sentinel node to traverse the whole linked list. When the sentinel node is null, a size value is returned.

  //Get the length of the single linked list
    public int size(){
        int count = 0;
        NodeList cur = this.head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

4. Find whether to specify whether the element is in the single linked list

This needs to build a method with boolean type as the return value. First, we should establish a sentinel node and traverse the whole linked list. If the value stored in a node is the same as the specified element, it will return True. After traversing the linked list, it will return False if it has not been found

  //Check whether the keyword is included and whether the key is in the single linked list
    public boolean contains(int key){
        NodeList cur = this.head;
        while(cur != null){
            if(cur.date == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

5. Insert an element at the specified position in the linked list

Like the sequence table, there are three cases

(1) . tail insertion

This is the simplest insertion method. Just point the next of the last node to the new node

 

 //Tail interpolation
    public void addLast(int num){
        NodeList nodeList = new NodeList(num);
        if(this.head == null){
            this.head = nodeList;
        }else{
            NodeList cur = this.head;
            while(cur.next != null){
                cur = cur.next;
            }//cur == null
            cur.next = nodeList;
        }
    }

(2) head insertion

For head insertion, we need to consider the problem of head pointer. We can solve it in two steps:

The first step is to point the next pointer of the new node to the head pointer of the original linked list.

The second step is to change the new node into a new header pointer.

 

 

 //Head insertion
    public void addFirst(int num){
        NodeList nodeList = new NodeList(num);//Create a node first
        nodeList.next = this.head;
        this.head = nodeList;
    }

(3) middle insertion

The middle insertion is also divided into two steps:

Step 1: the next pointer of the new node, pointing to the insertion position

In the second part, the next pointer of the front node at the insertion position points to the new node

/**
     * Find the address of the node at index-1
     * @param index
     * @return
     */
    public NodeList findIndex(int index){
        NodeList cur = this.head;
        while(index - 1 != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

    /**
     *
     * @param index Insertion position
     * @param num Insert element
     *  We can judge first, then find and then insert
     */
    //Insert at any position, and the first data node is subscript 0
    public void addIndex(int index,int num) {
        if (index < 0 || index > size()) {
            System.out.println("erro");
            return;
        }
        if(index == size()){
            addFirst(num);
            return;
        }
        if(index == size()){
            addLast(num);
            return;
        }
        NodeList nodeList = new NodeList(num);
        NodeList cur = findIndex(index);
        nodeList.next = cur.next;
        cur.next = nodeList;
    }

6. Delete the first occurrence of the specified element in the linked list

Deleting elements and adding elements are similar. They are also three methods

(1) . tail deletion

The simplest way to delete the tail is to direct the next point of the penultimate node to null

(2) header deletion

Set the original head node of the linked list as the next pointer of the original head node

(3) intermediate deletion

Point the next pointer of the front-end machine node of the node to be deleted to the next pointer of the element to be deleted

The premise is that we need to build a method to find the subscript of the previous node of the element to be deleted, so that we can use the next of the node to directly point to the next of the deleted element

 /**
     * Find the precursor of the keyword to delete
     * @param key
     * @return
     */
    public NodeList searchPerv(int key){
        NodeList cur = this.head;
        while(cur != null){
            if(cur.next.date == key){
                return cur;
            }//Note that cur next
            cur = cur.next;
        }
        return null;
    }
    //Delete the node whose keyword is key for the first time
    public void remove(int key){
        if(this.head == null){
            System.out.println("erro");
            return;
        }
        if(this.head.date == key){
            this.head = this.head.next;
            return;
        }
        NodeList cur = searchPerv(key);
        NodeList del = cur.next;
        cur.next = del.next;
    }

7. Printing of linked list

This is very simple. We just need to traverse the linked list and print the elements on the node in turn

(1) Print the whole linked list

    public void display(){
        NodeList cur = this.head;//cur to traverse the linked list
        while(cur != null){
            System.out.print(cur.date+" ");
            cur = cur.next;
        }
        System.out.println();
    }

(2) print the linked list from the given position

 /**
     * Print from the specified header node
     * @param newHead Given head node
     */
    public void display2(NodeList newHead){
         NodeList cur = newHead;
        while(cur != null){
            System.out.print(cur.date+" ");
            cur = cur.next;
        }
        System.out.println();
    }

8. Empty linked list

There will be a thorny problem in clearing the linked list, that is, if we release each reference from the first node and release null, but when we release the end point reference for the first time, we will find that the whole list is lost. At this time, we need to set up a sentry node. Before each release, we record the position of the head node, and then wait until the head node is released, We don't have to lose our previous position

   public void clear(){
        while (this.head != null) {
            NodeList curNext = head.next;
            this.head.next = null;
            this.head = curNext;
        }
    }

3, Summary

Through this article, we can find that in fact, the data structure is not so-called good or bad. The same is true for linked list and sequential list. It can be said that they have their own strengths and strengths. I have summarized the performance of linked list and sequential list in the following table

It is not difficult to find that the advantage of sequential list is to find and update an element, while the advantage of linked list is to insert and delete.

For the combination that needs to be searched and updated frequently, we choose the sequence table better.

For the combination that needs to be continuously inserted and deleted, we choose the linked list as the best.

Well, this article ends here. I'm glad to finish this article on the eve of Liverpool's upcoming finals. I hope Liverpool can win the championship!!! I'm Benni. I'll see you next time 😁😁😁😁😁

Tags: Java data structure linked list

Posted by FMB on Sun, 15 May 2022 08:47:29 +0300