# Linear table (array, linked list, queue, stack) detailed summary

Posted Jun 27, 20208 min read

Linear table is a very basic and important data structure, it mainly includes the following content:

• Array
• Queue
• Stack

Next, I will make a detailed summary of these four data structures, which implements dozens of common operations on linked lists. Hope it helps you.

1. Array

Array(Array) is a linear table data structure. It uses a continuous set of memory space to store a set of data with the same type.
Points to note:①. The array is a linear table; ②.Continuous memory space and the same type of data
Due to the second nature, the array supports "random access", according to the following table, the random access time complexity is O(1); but at the same time it makes deletion in the array, inserting data requires a lot of data movement jobs.

### Inefficient "insert" and "delete"

#### Insert operation

If the length of the array is n, we need to insert a piece of data into the kth position of the array, and we need to move the kth to nth elements sequentially one bit back.
The best case time complexity is O(1), which corresponds to inserting elements at the end of the array;
The worst-case time complexity is O(n), which corresponds to inserting elements at the beginning of the array;
The average time complexity is O(n), because we have the same probability of inserting elements at each position, so(1+2+3+...+n)/n=O(n);
But according to our needs, there is a specific scenario. If the data in the array is ordered, then we must do that when inserting; but if the data stored in the array does not have any rules, the array is just treated as a collection of stored data, we can have a The tricky way:
Move the kth element directly to the end of the array element, and put the new data directly into the kth position(it is not very simple), then the complexity of inserting the element is O(1).

#### Delete operation

As with the insert operation, in order to ensure the continuity of the memory, the delete operation also needs to move the data.
The best case time complexity is O(1), which corresponds to deleting the element at the end of the array;
The worst-case time complexity is O(n), which corresponds to deleting the element at the beginning of the array;
The average time complexity is O(n), because we have the same probability of deleting the element at each position, so(1+2+3+……+n)/n=O(n);
Of course, in some special cases, we do not necessarily have to perform complex delete operations. We just record the data that needs to be deleted, and pretend it was deleted. Until the array has no more space to store data, we can trigger another real delete operation.

This is actually similar to the trash bin in life. The trash has not disappeared, but it has been "marked" into trash, and it will not be cleaned until the trash bin is full.

### Beware of array access out of bounds

In the C language, as long as the memory is not restricted to access, all the memory space can be freely accessed. If negligence will cause serious consequences. Of course, Java will automatically detect.

• Representation of linked list nodes
• Singly linked list inserts nodes according to index
• Get the length of a singly linked list
• Print the length of singly linked list
• Single linked list deletes the specified index node
• Single linked list implements element search and returns whether there is Boolean value
• Singly linked list deletes the subsequent nodes of the specified index
• Recursively reverse singly linked lists
• Check if there is a ring in the linked list
• Delete the last kth node
• Seeking intermediate nodes

``````public class Node{
int data;
Node Next;
}``````
``````public class Method {
public static void PrintNode(Node list){
for(Node x=list;x!=null;x=x.Next)
System.out.print(x.data+" ");
System.out.println();
}``````

### Single linked list inserts nodes according to index

``````    public static Node insert(Node first,int index,Node a){
Node ret = new Node();
Node p=ret;
while((index--)!=0) p=p.Next;
//Complete the node insertion operation
a.Next=p.Next;
p.Next=a;
}``````

### Get the length of a singly linked list

``````    public static int GetLength(Node first){
int n=0;
for(Node x=first;x!=null;x=x.Next){
++n;
}
return n;
}``````
``````    public static void PrintLength(Node first){
System.out.println("Length:"+GetLength(first));
}``````

### Single linked list deletes the specified index node

``````    public static Node Delete(Node first,int index){
if(index<0||index>=GetLength(first)) return first;
else{
Node ret=new Node();
ret.Next=first;
Node p=ret;
while((index--)!=0) p=p.Next;
//Complete the deletion of the node
p.Next=p.Next.Next;
return ret.Next;
}
}``````

### Single linked list implements element search and returns whether there is a boolean value

``````    public static boolean Find(Node first,int key){
for(Node x=first;x!=null;x=x.Next){
if(x.data==key) return true;
}
return false;
}``````

### Single linked list deletes the subsequent nodes of the specified index

``````    public static void RemoveAfter(Node first,int index){
Node ret=new Node();
ret.Next=first;
Node p=ret;
while((index--)!=0) p=p.Next;
p.Next.Next=null;

}``````

``````    public static Node reverse(Node list){
Node curr=list,pre=null;
while(curr!=null){
Node next=curr.Next;
curr.Next=pre;
pre=curr;
curr=next;
}
return pre;
}``````

``````    public static Node reverseRecursively(Node head){
}``````

### Check if the linked list contains a ring

``````    public static boolean checkCircle(Node list){
if(list==null) return false;

Node fast=list.Next;
Node slow=list;

while(fast!=null&&fast.Next!=null){
fast=fast.Next.Next;
slow=slow.Next;

if(slow==fast) return true;
}
return false;
}``````

### Delete the last kth node

``````    public static Node deleteLastKth(Node list,int k){
//Using two pointers, fast and slow, there is a difference of k positions between them. If fast.Nest=null, it means that the position of slow is the penultimate k node
Node fast=list;
int i=1;
while(fast!=null&&i<k){
fast=fast.Next;
++i;
}

if(fast==null) return list;

Node slow=list;
Node prev=null;
while(fast.Next!=null){
fast=fast.Next;
prev=slow;
slow=slow.Next;
}

if(prev==null){
list=list.Next;
}else{
prev.Next=prev.Next.Next;
}
return list;
}``````

### Seeking intermediate nodes

``````    public static Node findMiddleNode(Node list){
if(list==null) return null;

Node fast=list;
Node slow=list;

while(fast!=null&&fast.Next!=null){
fast=fast.Next.Next;
slow=slow.Next;
}

return slow;
}``````

### Ordered list merge

``````    public static Node mergeTwoLists(Node l1,Node l2){
Node soldier=new Node();
Node p=soldier;

while(l1!=null&&l2!=null){
if(l1.data<l2.data){
p.Next=l1;
l1=l2.Next;
}
else{
p.Next=l2;
l2=l2.Next;
}
p=p.Next;
}

if(l1!=null){ p.Next=l1;}
if(l2!=null){ p.Next=l2;}
return soldier.Next;
}``````
1. Stack

• Sequential stack
• Chain stack

### 1. Sequential stack based on array implementation

• Constructor

• Push operation

• Stack operation

• Print operation

package Stack;

//Order stack based on array implementation
public class ArrayStack {

``````  private int[]items;
private int count;//The number of elements in the stack
private int n;//The size of the stack
//Initialize the array and apply for an array space of size n``````

public ArrayStack(int n){

``````  this.items=new int[n];
this.n=n;
this.count=0;``````

}

//Push operation
public boolean push(int item){

``````  //Insufficient array space, return false directly, failed to stack
if(count==n) return false;
//Place data in the subscript position, and count plus one
items[count]=item;
++count;
return true;``````

}

//Stack operation
public int pop(){

``````  //The stack is empty, return -1 directly;
if(count==0) return -1;
//Return the array element whose index is count-1, and count the number of elements in the stack minus one
int tmp=items[count-1];
--count;
return tmp;``````

}
public void PrintStack(){

``````  for(int i=count-1;i>=0;--i){
System.out.print(items[i]+" ");
}
System.out.println();
}``````

}

### 2. Chain stack based on linked list

• Push operation

• Stack operation

• Print operation

package Stack;

``````  private Node top;//Stack top(recently added elements)
private int N;//Number of elements
private class Node{
//The nested class that defines the node
int data;
Node Next;
}
public boolean isEmpty(){
}
public int size(){
return N;
}

public void push(int data){
/*Node newNode=new Node();
//Determine whether it is an empty stack
//if(top==null)
newNode=top;
top.data=data;
top.Next=newNode;
N++;*/
Node newNode=top;
top=new Node();
top.data=data;
top.Next=newNode;
++N;
}
public int pop(){
//Remove elements from the top of the stack
if(top==null) return -1;//Here we use -1 to indicate that there is no data in the stack
int data=top.data;
top=top.Next;
N--;
return data;
}
public void PrintStack(){
for(Node x=top;x!=null;x=x.Next){
System.out.print(x.data+" ");
}
System.out.println();
}``````

}

1. Ordinary queue

• Ordinary queue based on array
• Queue based on linked list
• Circular queue based on array

### 1. Ordinary queue based on array

• Constructor

• Enqueue operation

• Dequeue operation

• Print queue elements

package Queue;

//Use the array to implement the queue
public class ArrayQueue {

``````  //Array:items, array size:n
private int[]items;
private int n=0;
//head means the team head subscript, tail means the team tail subscript
private int tail=0;

//Apply an array of size capacity
public ArrayQueue(int capacity){
items=new int[capacity];
n=capacity;
}

//Entry(1), basic version
public boolean enqueue(int item){
//If tail==n, it means there is no more space at the end of the queue
if(tail==n) return false;
items[tail]=item;
++tail;
return true;
}

//Join the team(2), improved version
public boolean enqueue1(int item){
//If tail==n, it means there is no more space at the end of the queue
if(tail==n){
//tail==n&&head==0, indicating that the entire queue is full
//Data movement
}
//Renew the head and tail after moving
}
items[tail]=item;
++tail;
return true;
}

//Leave the team
public int dequeue(){
//If head==tail, the queue is empty
if(head==tail) return -1;//Here we use -1 to indicate that the queue is empty
return ret;
}

//Print queue
public void PrintQueue(){
System.out.print(items[i]+" ");
}
System.out.println();
}``````

}

### 2. Queue based on linked list

• Constructor

• Enqueue operation

• Dequeue operation

• Print queue elements

package Queue;

``````  private Node head;//Link to the earliest added node
private int N;//Number of elements in the queue
private class Node{
//The nested class that defines the node
int data;
Node Next;
}
public boolean isEmpty(){
}
public int size(){ return N;}

//Add elements to the end of the table, that is, enqueue
public void enqueue(int data){
Node newNode=tail;
tail=new Node();
tail.data=data;
tail.Next=null;
else newNode.Next=tail;
++N;
}
public int dequeue(){
//Remove the element from the table header
if(isEmpty()) tail=null;
N--;
return data;
}

//Print out the queue elements
public void PrintQueue(){
System.out.print(x.data+" ");
}
System.out.println();
}``````

}

### 3. Circular queue based on array

• Constructor

• Enqueue operation

• Dequeue operation

• Print queue elements

package Queue;

public class CircularQueue {

``````  //Array items, array size n
private int[]items;
private int n=0;
//head means the team head subscript, tail means the team tail subscript
private int tail=0;

//Apply an array of size capacity
public CircularQueue(int capacity){
items = new int[capacity];
n=capacity;
}

//Join the team
public boolean enqueue(int item){
//The queue is full
items[tail]=item;
tail=(tail+1)%n;//The cycle of counting
return true;
}

//Leave the team
public int dequeue(){
//If head==tail, the queue is empty
if(head==tail) return -1;//The queue is empty with -1
return ret;
}

//Print queue
public void PrintQueue(){
if(n==0) return;
System.out.print(items[i]+" ");
}
System.out.println();
}``````

}

## Explanation

There are too many article codes, I originally wanted to write them in several articles, but for some reason, they were put together in the end, which was slightly bloated. The code has been tested with test cases and there should be no errors.

If the experience is not good, you can move to my Github , which has a better look.

Off-topic:For beginners in algorithms, I recommend a very nice book "Fourth Edition of Algorithms", where the various maps are very detailed. If you need an electronic version of the file, reply Algorithm 4 in the background to get the download link. Reply in the background Algorithm 01 Send you a mind map of algorithm and data structure. Finally, I hope we can make progress together and grow together!