Introduction to bidirectional linked lists
A bidirectional list, in fact, means that each node in a linked list knows its previous node and its next node.
Each node has a precursor pointer and a rear-driver pointer, which store the address of the previous node and the next node in memory respectively.
Head points to the first valid node in the list.
Two, the realization of bidirectional linked list
1, insert,
The insertion operation of bidirectional linked list only needs to change the pointer pointing of adjacent nodes. Time complexity is O (1).
/** * inserts a new node into the specified node@paramPreNode Specifies the node *@paramNewNode newNode */
public void add(SNode<T> preNode, SNode<T> newNode) {
To insert to the end of the list, there is no need to maintain the precursor pointer to the next node
if(preNode.next ! =null) {
preNode.next.pre = newNode;
}
newNode.next = preNode.next;
newNode.pre = preNode;
preNode.next = newNode;
size++;
}
Copy the code2, remove,
The deletion of bidirectional linked list is different from other deletion operations. As long as you know the node to be deleted, you can delete it directly without looking for the previous node of the node to be deleted. Time complexity is O (1).
/** * removes the element ** whose data field is the specified value@param e
*/
public void del(T e) {
SNode<T> temp = head;
while(temp ! =null) {
if (temp.data.equals(e)) {
// Maintain head, head always points to the first valid node in the bidirectional list
temp.next.pre = temp.pre;
if (temp == head) {
head = head.next;
head.pre = null;
} else {
temp.pre.next = temp.next;
}
return;
}
// Temp moves backtemp = temp.next; }}Copy the codeThird, summary
A bidirectional linked list is a type of linked list in which each node has a precursor and a precursor. Store the address of the preceding node and the following node in memory respectively. The time complexity of both inserts and deletions is O (1).
4. Complete code
/** * The implementation of bidirectional lists **@author liyanan
* @date2020/1/2: * /
public class DoubleLinkedList<T> {
public static class SNode<T> {
/** * Store data */
public T data;
/** * points to the previous node of the current node */
public SNode<T> pre;
/** * points to the next node of the current node */
public SNode<T> next;
public SNode(a) {}public SNode(T data) {
this.data = data; }}/** * the base address of the first valid node */
private SNode<T> head;
/** * The number of valid nodes in the bidirectional list */
private int size;
public DoubleLinkedList(a) {
head = null;
size = 0;
}
public int getSize(a) {
return size;
}
public boolean isEmpty(a) {
return size == 0;
}
/** * insert node to end of bidirectional list **@param newNode
*/
public void addLast(SNode<T> newNode) {
if (isEmpty()) {
head = newNode;
head.next = null;
head.pre = null;
size++;
} else {
SNode<T> temp = head;
// Find the last valid node of the bidirectional list
while(temp.next ! =null) {
temp = temp.next;
}
// Add the new node to the bidirectional listadd(temp, newNode); }}/** * inserts a new node into the specified node@paramPreNode Specifies the node *@paramNewNode newNode */
public void add(SNode<T> preNode, SNode<T> newNode) {
To insert to the end of the list, there is no need to maintain the precursor pointer to the next node
if(preNode.next ! =null) {
preNode.next.pre = newNode;
}
newNode.next = preNode.next;
newNode.pre = preNode;
preNode.next = newNode;
size++;
}
/** * removes the element ** whose data field is the specified value@param e
*/
public void del(T e) {
SNode<T> temp = head;
while(temp ! =null) {
if (temp.data.equals(e)) {
// Maintain head, head always points to the first valid node in the bidirectional list
temp.next.pre = temp.pre;
if (temp == head) {
head = head.next;
head.pre = null;
} else {
temp.pre.next = temp.next;
}
return;
}
// Temp moves backtemp = temp.next; }}/** * delete node ** at specified position@param k
*/
public void del(int k) {
SNode<T> delNode = find(k);
delNode.next.pre = delNode.pre;
if (delNode == head) {
head = head.next;
head.pre = null;
} else{ delNode.pre.next = delNode.next.next; }}/** * find the KTH node of the bidirectional list **@paramK, k starts at 0 *@return* /
public SNode<T> find(int k) {
if (k > size || k < 0) {
throw new RuntimeException("The parameter k passed in must be greater than or equal to zero and less than or equal to the length of the list size.");
}
int cnt = 0;
SNode<T> t = head;
while(cnt ! = k) { cnt++; t = t.next; }return t;
}
/** * Prints all valid nodes ** of the single-linked list@return* /
public String printAll(a) {
StringBuilder sb = new StringBuilder();
SNode<T> temp = head;
while(temp ! =null) {
sb.append(temp.data);
sb.append("");
temp = temp.next;
}
return sb.toString();
}
public static void main(String[] args) {
DoubleLinkedList<Integer> doubleLinkedList = new DoubleLinkedList<>();
SNode<Integer> node1 = new SNode<>(1);
SNode<Integer> node2 = new SNode<>(2);
SNode<Integer> node3 = new SNode<>(3);
SNode<Integer> node4 = new SNode<>(4);
SNode<Integer> node5 = new SNode<>(5);
doubleLinkedList.addLast(node1);
doubleLinkedList.addLast(node2);
doubleLinkedList.addLast(node3);
doubleLinkedList.addLast(node4);
doubleLinkedList.addLast(node5);
System.out.println(Insert five nodes:);
System.out.println(doubleLinkedList.printAll());
System.out.println(Insert a new node after the fourth node:);
SNode<Integer> node6 = new SNode<Integer>(6);
doubleLinkedList.add(node4, node6);
System.out.println(doubleLinkedList.printAll());
System.out.println(Insert a new node after the first node:);
SNode<Integer> node7 = new SNode<Integer>(7);
doubleLinkedList.add(node1, node7);
System.out.println(doubleLinkedList.printAll());
System.out.println("Delete node with value 1:);
doubleLinkedList.del(Integer.valueOf(1));
System.out.println(doubleLinkedList.printAll());
System.out.println("Delete node with value 3:");
doubleLinkedList.del(Integer.valueOf(3));
System.out.println(doubleLinkedList.printAll());
System.out.println("Delete node with value 6:);
doubleLinkedList.del(Integer.valueOf(6));
System.out.println(doubleLinkedList.printAll());
System.out.println("Delete the first node");
doubleLinkedList.del(0); System.out.println(doubleLinkedList.printAll()); }}Copy the code