Linked storage structure -- implementation of one-way linked list (Java)

Data structure - one way linked list

preface

In the previous chapter, we implemented the linear table using the sequential storage structure. We found that the query efficiency of the linear table is very fast and the time complexity is O(1), but the efficiency of adding and deleting data is relatively low. Based on these problems, this article will discuss how to use another storage structure to realize linear list chain storage structure.

1, What chain storage structure?

Chained storage structure is a non continuous and non sequential storage structure of physical storage units. The physical and logical order of data elements is realized through the pointer connection order in the linked list. The linked list is composed of a series of nodes. Each node is divided into data field (data) and pointer field (next). The data field is used to store data. The pointer field points to the next node, which can be generated dynamically at run time. (as shown in the figure)

2, Realization idea of one-way linked list

(in this article, we will first focus on the one-way linked list, and then discuss the double linked list in the next chapter)
Insert data:

Delete data:

3, Implementation code

package sequence;


import java.util.Iterator;

public class LinkList<T> implements Iterable<T>{
    //Record header node
    private Node head;
    //Record the length of the linked list
    private int N;

    //Head node inner class
    private class Node {
        //Data domain
        T item;
        //Pointer field
        Node next;

        public Node(T item,Node next){
            this.item = item;
            this.next = next;
        }
    }

    public LinkList(){
        //Initialize header node
        this.head = new Node(null,null);
        //Number of initialization elements
        this.N = 0;
    }

    //Empty linked list
    public void clear(){
        head.next = null;
        this.N = 0;
    }

    //Get linked list length
    public int getLength(){
        return N;
    }

    //Determine whether the linked list is empty
    public  boolean isEmpty(){
        return this.N == 0;
    }

    //Gets the element at the specified location i
    public T get(int i){
        Node n = head.next;
        //Through the loop, look back from the node to find the corresponding element for the i-th time
        for (int index = 0; index < i; index++) {
            n = n.next;
        }
        return n.item;
    }

    //Add data to linked list
    public void insert(T t){
        //Find the last node of the current element;
        Node n = head;
        while (n.next != null){
            n = n.next;
        }
        //Create new elements t and nodes:
        Node newNode = new Node(t, null);
        //Make the current last element node point to the new node:
        n.next = newNode;
        //Number of elements + 1:
        N++;

    }

    //Add element before the ith element in the linked list
    public  void insert(int i,T t){
        //Find the node before i location:
        Node pre = head;
        for(int index = 0;index < i ;index++){
            pre = pre.next;
        }
        //Locate i location node:
        Node curr = pre.next;
        //Create a new node, save the new element t, and point the pointer field of the new node to the i position:
        Node newNode = new Node(t,curr);
        //Make the node before i point to the new element node:
        pre.next = newNode;
        //Number of elements + 1:
        N++;

    }

    //Delete and return the ith element in the linear table
    public T remove(int i){
        //Find the previous node at i location:
        Node pre = head;
        for(int index = 0;index < i ;index++){
            pre = pre.next;
        }
        //Find node at i location:
        Node curr = pre.next;
        //Find the next node at i location:
        Node NeNode = curr.next;
        //Make the previous node of position i point to the next node of position i:
        pre.next = NeNode;
        //Number of elements - 1:
        N--;
        return curr.item;
    }

    //Returns the index of the first occurrence of the specified element in a linear table
    public int indexOf(T t){
        //Search from the beginning:
        Node n = head;
        for (int index = 0;n.next != null;index++){
            n = n.next;
            if(n.item.equals(t)){
                return index;
            }
        }
        return -1;
    }

    //Provide traversal mode:
    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }
    private class LIterator implements Iterator{
        private Node n;
        public LIterator(){
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }
}

Note: we implement the Node class Node through internal classes, and use the constructor to initialize its member variables; The implementation of providing traversal mode has been described in detail in the previous article (implementation of data structure sequence table) (click here to view) It will not be repeated here.

summary

Through the discussion of sequential list and linked list, we can find that the advantages of linked list are: the position of linked list in memory is discontinuous, which can apply for and release space on demand without wasting space; At the same time, it is no longer applicable to the whole-body linked list, because it is less efficient to access the data in the same order as the sub linked list. At the same time, it is no longer applicable to the sub linked list, but it is no longer applicable to the sub linked list.

Tags: Java Algorithm data structure linked list

Posted by csueiras on Sun, 15 May 2022 01:28:35 +0300