current position：Home>Simple implementation of linked list in Java

In my last article, I explained the sequence table in detail , We can know that the sequential table is stored sequentially in memory , But the list that we will explain in this article is just the opposite , Linked lists are stored randomly in memory , This is also a sideshow of , Linked list is very flexible , It can make rational use of a lot of space , And through some “ Secret signal ” To realize their respective connections .

1、 What does the linked list look like ？

A linked list is composed of nodes , These nodes are just like train carriages , Connect one by one , The following figure is a linked list

2、 What is the node ？

The linked list is composed of one node, as shown in the following figure , The storage of each data in the linked list consists of the following two parts ：

The data element itself , The area where it is located is called the data field ;
A pointer to the immediate successor element , The area where the pointer is located is called the pointer field ;

And our linked list is linked by nodes , According to the above figure, it is not difficult for us to find that a node must have two parts , One to store data , One to save 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 .

Two 、 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 in building a linked list is, of course, to lay the foundation , Set up nodes , We can create a class to realize the creation of a node , Then assign values to the nodes by constructing the method of assignment , Of course, this reference must be a 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、 The construction of linked list

With nodes, we can build a linked list , First , A linked list must have a header node , If there is no head node, there will be no head of the group of dragons , All linked list data is lost , So this head node is very important , Then initialize the linked list , In fact, it is not the same as the construction of nodes , I also use a construction method to define the beginning of a linked list , But the construction method of nodes is to assign values to nodes , 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. Check the 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 when , Return to one size value .

  // 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 requires building a method with boolean type as the return value , First of all, we should establish a sentinel node , Traverse the entire list , If a node stores the same value as the specified element , return True, After traversing the linked list, it returns... Before it is found False

  // Look for keywords key Is it in a 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 a specified location in the linked list

This is the same as the sequence table , There are three situations

（1）、 Tail insertion

This is the simplest way to insert , Directly put the of the last node next Just point to the new node

 // The 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

Head insertion we need to consider the problem of head pointer , We can probably solve it in two steps ：

First step , Put the new node next The pointer points to the head of the original linked list .

The second step , Change the new node into a new header pointer .

 // The first interpolation 
    public void addFirst(int num){
        NodeList nodeList = new NodeList(num);// First create a node 
        nodeList.next = this.head;
        this.head = nodeList;
    }

（3）、 Intermediate insertion

The middle insertion is also divided into two steps ：

First step 、 New node next The pointer , Pointer to the insertion position

Second parts 、 Insert the position of the front node next The pointer , Point to the new node

/**
     *  find index-1 The address of the node of the location 
     * @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 elements 
     *   We can judge first, then look for and then insert 
     */
    // Insert at any position , The first data node is 0 Subscript no. 
    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 much the same , There are also three ways

（1）、 Tail delete

Tail deletion is the simplest , Put the... Of the penultimate node next The direct point is null

（2）、 Head delete

Set the original head node of the linked list to the original head node next Just a pointer

（3）、 Delete... In the middle

Put the front-end machine node of the node to be deleted next The pointer , Point to the element to delete next Just a pointer

The premise is that we need to build a method to find the subscript of the previous node of the element to be deleted , In this way, we can get the node's next Point directly to the... Of the deleted element next

 /**
     *  find   The precursor of the keyword to be deleted 
     * @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 first keyword as key The node of 
    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 , Print the elements on the node in turn

（1）、 Print the whole 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 the list

There will be a thorny problem in clearing the linked list , That is, if we release every reference from the node null, But when we release the end point reference for the first time, we will find that the whole linked list is lost , At this time, we need to set up a sentinel node , Before each release, we record the position of the header node , Then, after 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、 ... and 、 summary

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

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

For the combination with relatively high frequency of continuous search and update , It's better for us to choose the sequence table .

For combinations that need to be continuously inserted and deleted , We choose the best linked list .

Okay , This article is over here , I'm glad to finish this article on the eve of Liverpool's upcoming finals , I hope Liverpool can win the title ！！！ I am a banni, See you next time

copyright notice
author[banbanbanni],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/135/202205142226455441.html