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
  • Linked list
  • 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.

  1. Linked list

  • Representation of linked list nodes
  • Print singly linked list
  • 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
  • Single linked list reversal
  • Recursively reverse singly linked lists
  • Check if there is a ring in the linked list
  • Delete the last kth node
  • Seeking intermediate nodes
  • Ordered linked list merge

Linked list node representation

public class Node{
    int data;
    Node Next;
}
public class Method {
    //Print singly linked list
    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();
        ret.Next=first;//Create a virtual head node
        Node p=ret;
        while((index--)!=0) p=p.Next;
        //Complete the node insertion operation
        a.Next=p.Next;
        p.Next=a;
        //Return the address of the real linked list head node
        return ret.Next;//The function returns the head node of the linked list
    }

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;

    }

Single Linked List Reverse

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

Single-linked list recursively

    public static Node reverseRecursively(Node head){
        if(head==null||head.Next==null) return head;//Recursive termination condition, return the head node of the reversed list
        Node reversedListHead=reverseRecursively(head.Next);
        head.Next.Next=head;//Change the pointing order between these two nodes
        head.Next=null;
        return reversedListHead;//Return the reversed list head node
    }

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;

    public class LinkedListStack {

      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(){
          return top==null;
      }
      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 head=0;
      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
              if(head==0) return false;
              //Data movement
              for(int i=head;i<tail;++i){
                  items[i-head]=items[i];
              }
              //Renew the head and tail after moving
              tail=tail-head;
              head=0;
          }
          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
          int ret=items[head];
          ++head;
          return ret;
      }
    
      //Print queue
      public void PrintQueue(){
          for(int i=head;i<tail;++i){
              System.out.print(items[i]+" ");
          }
          System.out.println();
      }

    }

2. Queue based on linked list

  • Constructor

  • Enqueue operation

  • Dequeue operation

  • Print queue elements

    package Queue;

    //Queue based on linked list
    public class LinkedListQueue {

      private Node head;//Link to the earliest added node
      private Node tail; //link to the recently 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(){
          return head==null;
      }
      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;
          if(isEmpty()) head=tail;
          else newNode.Next=tail;
          ++N;
      }
      public int dequeue(){
          //Remove the element from the table header
          int data=head.data;
          head=head.Next;
          if(isEmpty()) tail=null;
          N--;
          return data;
      }
    
      //Print out the queue elements
      public void PrintQueue(){
          for(Node x=head;x!=null;x=x.Next){
              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 head=0;
      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
          if((tail+1)%n==head) return false;
          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
          int ret=items[head];
          head=(head+1)%n;
          return ret;
      }
    
      //Print queue
      public void PrintQueue(){
          if(n==0) return;
          for(int i=head;i%n!=tail;i=(i+1)%n){
              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!