Use of Java linked list

Preface

Explain:

  • Language: Java
  • Environment: IntelliJ IDEA
  • JDK Version: 1.8
  • Source code: GitHub
  • The insertion, query and sorting of linked lists usually involve algorithms. This paper focuses on exploring linked lists, not algorithms, so the code is written in the most easy-to-understand way.

Before learning how to use Java linked lists, you need to understand the use of Java reference types.

int a = 10;
int b = a;
b++;
System.out.println(a);

The result of the above code is: 10. In int b = a; in this operation, the value of a is actually assigned to b, so b++; it does not affect the value of a, which is a feature of the basic data type.

//Employee is an entity class that describes employee information
Employee employee1 = new Employee(1,"xiaoming",30);
Employee employee2 = employee1;
employee2.seteName("liumei");
System.out.println(employee1.toString());

The result of the above code is: Employee{eId=1, eName='liumei', eAge=30}. This means that Employee employee2 = employee1; in operation, employee1 and employee2 share the same data, so any change of data in either variable will affect the other.

In fact, new is to divide a space in memory to store data, and the employee1 variable receiving new is just a pointer to this memory space. When assigning this variable to employee2, employee2 will also be a pointer to the same memory space as employee1. Therefore, both variables are actually manipulated. It is an operation on the same memory space.

Singly Linked List

Characteristic:

  • Have next pointer to the next node
  • Only one-way operation list from the beginning node
  • Inserting nodes at the head of the list is efficient, but inserting nodes at the tail of the list is inefficient.

Insert node:

     /**
     * Insert data at the end of the list
     */
    public boolean addLast(Employee employee){
        Node node = new Node(employee); //Create the node to insert
        Node temp = this.head;  //Create a secondary pointer to the head node
        while (true){   //Move the auxiliary pointer to the last node of the current list
            if(temp.next==null){break;}
            temp = temp.next;
        }
        temp.next = node;   //Insert the node to be inserted at the end of the list
        this.length++;
        return true;
    }

    /**
     * Insert data at the head of the list
     */
    public boolean addFirst(Employee employee){
        Node node = new Node(employee); //Create the node to insert
        Node temp = this.head;  //Create a secondary pointer to the head node
        if(isEmpty()){    //Empty list
            this.head.next = node;  //Insert nodes directly after head
        }else{  //The list is not empty
            temp = temp.next;   //Move temp to the first valid node
            this.head.next = node;  //After inserting the inserting node into the head node
            node.next = temp;   //Connect other nodes to newly inserted nodes
        }
        this.length++;
        return true;
    }

    /**
     * Insert the node after the index node, and the index starts at 0
     */
    public boolean addIndex(Employee employee,int index){
        if(isEmpty()||index>=this.length||index<0){ return false;}//Insertion failure if empty linked list and index format range are incorrect
        Node node = new Node(employee); //Create the node to insert
        Node temp = this.head;  //Create a secondary pointer to the head node
        for (int i = 0;i<=index;i++){   //Move the auxiliary pointer to the target node
            temp = temp.next;
        }
        node.next = temp.next;  //Let the next of the new node point to the node after the target node
        temp.next = node;   //Let the auxiliary pointer point to the new node
        this.length++;
        return true;
    }

Delete nodes:

     /**
     * Delete the last node
     */
    public boolean deleteLast(){
        if(isEmpty()){return false;}
        Node temp = this.head;  //Create a secondary pointer to the head node
        while (true){   //Move the auxiliary pointer to the previous node of the last node in the current list
            if(temp.next.next==null){break;}
            temp = temp.next;
        }
        temp.next = null;   //Disconnect from the last node
        this.length--;
        return true;
    }

    /**
     * Delete the first node
     */
    public boolean deleteFirst(){
        if(isEmpty()){return false;}
        Node temp = this.head.next;  //Create a secondary pointer to the first valid node
        this.head.next = temp.next; //Connect the header node to the node after the first valid node
        this.length--;
        return true;
    }

    /**
     * Delete the specified index node, the index starts at 0
     */
    public boolean deleteIndex(int index){
        if(isEmpty()||index>=this.length||index<0){ return false;}//Failure to delete empty linked list and incorrect index format range
        Node temp = this.head;  //Create a secondary pointer pointer node
        for (int i = 0;i<index;i++){    //Move the auxiliary pointer to the node before the target node
            temp = temp.next;
        }
        temp.next = temp.next.next; //Let the auxiliary pointer point to the node after the target node
        this.length--;
        return true;
    }

Query node:

    /**
     * Look at the data at the index location. The index starts at 0.
     */
    public Employee getEmployee(int index){
        if(isEmpty()||index>=this.length||index<0){ return null;}//Query failure if empty linked list and index format range are incorrect
        Node temp = this.head;  //Create a secondary pointer pointer node
        for (int i = 0;i<=index;i++){    //Move the auxiliary pointer to the target node
            temp = temp.next;
        }
        return temp.data;   //Return data
    }

Modifying nodes: Similar to queries, rules need to be customized

Bidirectional linked list

Characteristic:

  • Have next pointer and previous pointer, next pointer to the next node, previous pointer to the previous node
  • Allow bidirectional operation of linked list
  • Two-way linked lists usually have a head and a tail, so inserting data from both ends is efficient.
  • Since two-way operation of linked list is allowed, the query efficiency is higher than that of single linked list.

Insert node:

    /**
     * Insert data at the end of the list
     */
    public boolean addLast(Employee employee){
        Node node = new Node(employee); //Create the node to insert
        if(isEmpty()){  //If the list is empty
            this.head.next = node;  //Connect the head and last nodes to the node
            this.last.pre = node;
            node.next = this.last;  //Connect the next and pre of node to last and head
            node.pre = this.head;
        }else{  //If the list is not empty (pay attention to the order)
            node.next = this.last;  //Connect node to last and current last node
            node.pre = this.last.pre;
            this.last.pre.next = node;  //Connect last to the current last node
            this.last.pre = node;
        }
        this.length++;
        return true;
    }

    /**
     * Insert data at the head of the list
     */
    public boolean addFirst(Employee employee){
        Node node = new Node(employee); //Create the node to insert
        if(isEmpty()){  //If the list is empty
            this.head.next = node;  //Connect the head and last nodes to the node
            this.last.pre = node;
            node.next = this.last;  //Connect the next and pre of node to last and head
            node.pre = this.head;
        }else{  //If the list is not empty (pay attention to the order)
            node.next = this.head.next;  //Connect node to head and the current first node
            node.pre = this.head;
            this.head.next.pre = node;  //Connect the head to the current first node
            this.head.next = node;
        }
        this.length++;
        return true;
    }

    /**
     * Insert the node after the index node, and the index starts at 0
     */
    public boolean addIndex(Employee employee,int index){
        if(isEmpty()||index>=this.length||index<0){return false;}//Insertion failure if empty linked list and index format range are incorrect
        Node node = new Node(employee);;
        Node temp;
        if((index+1)<=this.length/2){   //If the insertion position is less than half the total length of the list, insert in the first half
            temp = this.head;
            for (int i = 0;i<=index;i++){
                temp = temp.next;
            }
            node.next = temp.next;
            node.pre = temp;
            temp.next.pre = node;
            temp.next = node;
        }else{  //If the insertion position is greater than half the total length of the list, insert in the second half
            temp = this.last;
            for (int i = 0;i<=this.length-(index+1);i++){
                temp = temp.pre;
            }
            node.next = temp.next;
            node.pre = temp;
            temp.next.pre = node;
            temp.next = node;
        }
        this.length++;
        return true;
    }

Delete nodes:

    /**
     * Delete the last node
     */
    public boolean deleteLast(){
        if(isEmpty()){return false;}
        this.last.pre.pre.next = this.last; //Point next of the previous node of the last node to last
        this.last.pre = this.last.pre.pre;//Point last pre to the previous node of the last node
        this.length--;
        return true;
    }

    /**
     * Delete the first node
     */
    public boolean deleteFirst(){
        if(isEmpty()){return false;}
        this.head.next.next.pre = this.head;//Point the pre of the last node of the first node to the head
        this.head.next = this.head.next.next;//Point the next of the head to the next of the first node
        this.length--;
        return true;
    }

    /**
     * Delete the specified index node, the index starts at 0
     */
    public boolean deleteIndex(int index){
        if(isEmpty()||index>=this.length||index<0){return false;}//Failure to delete empty linked list and incorrect index format range
        Node temp;
        if((index+1)<=this.length/2){   //If the insertion position is less than half the total length of the list, the first half of the list is deleted.
            temp = this.head;
            for (int i = 0;i<=index;i++){
                temp = temp.next;
            }
            temp.pre.next = temp.next;
            temp.next.pre = temp.pre;
        }else{  //If the insertion position is greater than half the total length of the list, delete in the second half
            temp = this.last;
            for (int i = 0;i<=this.length-(index+1);i++){
                temp = temp.pre;
            }
            temp.pre.next = temp.next;
            temp.next.pre = temp.pre;
        }
        this.length--;
        return true;
    }

Find nodes:

    /**
     * Look at the data at the index location. The index starts at 0.
     */
    public Employee getEmployee(int index){
        if(isEmpty()||index>=this.length||index<0){return null;}//Failure to delete empty linked list and incorrect index format range
        Node temp;
        if((index+1)<=this.length/2){   //If the insertion position is less than half the total length of the list, look for it in the first half of the list.
            temp = this.head;
            for (int i = 0;i<=index;i++){
                temp = temp.next;
            }
            return temp.data;
        }else{  //If the insertion position is greater than half the total length of the list, look for it in the latter half of the list.
            temp = this.last;
            for (int i = 0;i<=this.length-(index+1);i++){
                temp = temp.pre;
            }
            return temp.data;
        }
    }

Modifying nodes: Similar to queries, rules need to be customized

Circular linked list

Characteristic:

  • Have next pointer to the next node
  • The next of the last node of the list points to the first node, forming a loop.
  • In order to achieve the integrity of a ring, a circular list usually does not need a header node.
  • Only one cycle in one direction.

The addition, deletion and modification of circular linked list need to be determined according to the requirements. The general implementation can be analogous to the single linked list connecting the next of the last node to the first node. In fact, you need to customize where to insert, where to delete, and what conditions to determine the cycle and the cycle termination.

list

Characteristic:

  • Have next pointer and previous pointer, next pointer to the next node, previous pointer to the previous node
  • The next of the last node of the list points to the first node, and the previous of the first node points to the last node, forming a loop.
  • In order to achieve the integrity of a ring, a circular list usually does not need a header node.
  • Two-way loops are possible

The addition, deletion and modification of bi-directional circular list need to be determined according to the requirements. The general implementation can be analogous to connecting the next of the last node to the first node, and the previous of the first node to the bi-directional list of the last node. In fact, you need to customize where to insert, where to delete, and what conditions to determine the cycle and the cycle termination.

Tags: Programming Java less IntelliJ IDEA JDK

Posted on Thu, 05 Sep 2019 00:24:43 -0700 by Lol5916