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