# 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;

//Record the length of the linked list
private int N;

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

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

//Number of initialization elements
this.N = 0;
}

public void clear(){
this.N = 0;
}

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){
//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;
}

public void insert(T t){
//Find the last node of the current element;
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++;

}

public  void insert(int i,T t){
//Find the node before i location:
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:
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:
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(){
}

@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.

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