Bidirectional linked list, also known as double linked list, is a kind of linked list. There are two pointers in each data node, pointing to the direct precursor and direct successor respectively. Therefore, starting from any node in the two-way linked list, it is convenient to directly access its predecessor node and successor node with address.

Here, we define the bidirectional circular linked List as the LinkedList class and implement the List, Deque and Stack interfaces

Here we mainly talk about the principles of several aspects,

If you are adding element node objects directly, you can add them directly

}

If it is added through index, four situations should be considered:

First, judge whether the index of the linked list is out of bounds. If it is out of bounds, throw an out of bounds exception

if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("index outof range");
}
First case
When the linked list is empty
Because it is a two-way circular linked list tail Successor to next point head,head Precursor of pre point tail

The code is as follows

if (isEmpty()) {
tail = node;
}
The second case
take node Defined as a new header node

The code is as follows:

else if (index == 0) {
The third case
take node.next point tail.next
tail.next point node
node.pre point tail
take node Define as new tail Tail node
The linked list after successful addition at the end is as follows:

The code is as follows:

else if (index == size) {
node.next = tail.next;
tail.next = node;
node.pre = tail;
tail = node;
The fourth case
First, we need to define two pointers, p The node is the precursor of the added node, q The node is a node next The next hop is also the next hop for adding nodes
First of all, the location of the added node should be considered. If the inserted node is in size/2 The default position is on the left, from head Start pointing back
Define two nodes p,q
p point p.next
q point p.next
p.next point node
node.pre point p
node.next point q
last q.pre point node

The node addition is completed as shown in the figure below:

The code is as follows:
Node p,q;
if (index <= size / 2) {
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
q = p.next;
p.next = node;
node.pre = p;
node.next = q;
q.pre = node;

Then the added position is close to the tail node
First, point p to the tail node of tai
Then p=p.pre
q points to p.pre
q.next points to node
p.pre points to node
Finally, node Next points to p
After adding nodes, see the figure below:

The code is as follows:

else {
p = tail;
for (int i = size - 1; i > index; i--) {
p = p.pre;
}
q = p.pre;
q.next = node;
node.pre = q;
p.pre = node;
node.next = p;
}

## 2, Delete node

The first thing is to delete the element directly
Find the location of the element to be deleted through the indexOf method
As long as the position is not - 1, it will be deleted directly

public void remove(E element) {
int index = indexOf(element);
if (index != -1) {
remove(index);
}
}

If it is deleted through index
Like adding, first judge whether the index is out of bounds, and then consider the location of deletion
There are four major situations:
Only one node
First, define a ret to store the deleted node
Directly set the head to null
Set tail to null

if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("index outof range");
}
E ret = null;
if (size == 1) {
tail = null;
}

Delete from scratch node
First point node to head next;
As shown below:
Define a node node

Disconnect all connections of the beginning node

This is the case after complete deletion

The code is as follows:

else if (index == 0) {
}

Delete from tail node
node points to tail pre
ret=tail.data
tail.pre set null
node.next points to tail next
tail.next empty
tail points to node
Finally, head Pre points to tail
As shown below:
Before deletion:

Disconnect all contacts:

After deletion:

The code is as follows:

else if (index == size - 1) {
Node node = tail.pre;
ret = tail.data;
tail.pre = null;
node.next = tail.next;
tail.next = null;
tail = node;
}

Delete from middle
If you delete from the middle, you have to consider the approximate location of the deleted node as you add
Define three nodes p,q,r
p is the previous node to delete
q is the node to be deleted
r is the last node to be deleted
When the node to be deleted is on the left
Then move to p.next
Then point q to p.next
Give the value of q.data to ret
r points to q.next
p.next points to r
r.pre points to p
q.next empty
q.pre empty
As shown below:

After deletion:

The code is as follows:

else {
Node p,q,r;
if (index <= size / 2) {
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
q = p.next;
ret = q.data;
r = q.next;
p.next = r;
r.pre = p;
q.next = null;
q.pre = null;
}

Then, the node to be deleted is close to the tail node
P move left p=p.next
q points to p.pre
Give q.data to ret
r points to q.pre
r.next points to p
p.pre points to r
q.next empty
q.pre empty
Just like adding, in any case, if deleted, the overall length of the linked list is - 1, that is, size - and finally ret is returned
As shown in the figure:

After deletion:

The code is as follows:

else {
p = tail;
for (int i = size - 1; i > index; i--) {
p = p.pre;
}
q = p.pre;
ret = q.data;
r = q.pre;
r.next = p;
p.pre = r;
q.next = null;
q.pre = null;
}
}
size--;
return ret;
}

The whole code is as follows:

public class LinkedList<E> implements List<E>, Stack<E>, Queue<E>, Deque<E> {
private class Node {
E data;
Node pre;
Node next;
public Node(E data) {
this.data = data;
pre = null;
next = null;
}
@Override
public String toString() {
return data.toString();
}
}
private Node tail;
private int size;

tail = null;
size = 0;
}

@Override
}

@Override
public void add(int index, E element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("index outof range");
}
Node node = new Node(element);
if (isEmpty()) {
tail = node;
} else if (index == 0) {
} else if (index == size) {
node.next = tail.next;
tail.next = node;
node.pre = tail;
tail = node;
} else {
Node p,q;
if (index <= size / 2) {
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
q = p.next;
p.next = node;
node.pre = p;
node.next = q;
q.pre = node;
} else {
p = tail;
for (int i = size - 1; i > index; i--) {
p = p.pre;
}
q = p.pre;
q.next = node;
node.pre = q;
p.pre = node;
node.next = p;
}
}
size++;
}

@Override
public void remove(E element) {
int index = indexOf(element);
if (index != -1) {
remove(index);
}
}

@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("index outof range");
}
E ret = null;
if (size == 1) {
tail = null;
} else if (index == 0) {
} else if (index == size - 1) {
Node node = tail.pre;
ret = tail.data;
tail.pre = null;
node.next = tail.next;
tail.next = null;
tail = node;
} else {
Node p,q,r;
if (index <= size / 2) {
for (int i = 0; i < index - 1; i++) {
p = p.next;
}
q = p.next;
ret = q.data;
r = q.next;
p.next = r;
r.pre = p;
q.next = null;
q.pre = null;
} else {
p = tail;
for (int i = size - 1; i > index; i--) {
p = p.pre;
}
q = p.pre;
ret = q.data;
r = q.pre;
r.next = p;
p.pre = r;
q.next = null;
q.pre = null;
}
}
size--;
return ret;
}

@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
} else if (index == size - 1) {
return tail.data;
} else {
for (int i = 0; i < index; i++) {
p = p.next;
}
return p.data;
}
}

@Override
public E set(int index, E element) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("index outof range");
}
E ret = null;
if (index == 0) {
} else if (index == size - 1) {
ret = tail.data;
tail.data = element;
} else {
for (int i = 0; i < index; i++) {
p = p.next;
}
ret = p.data;
p.data = element;
}
return ret;
}

@Override
}

@Override
}

@Override
public E removeFirst() {
return remove(0);
}

@Override
public E removeLast() {
return remove(size - 1);
}

@Override
public E getFirst() {
return get(0);
}

@Override
public E getLast() {
return get(size - 1);
}

@Override
public void offer(E element) {
}

@Override
public E poll() {
return remove(0);
}

@Override
public E element() {
return get(0);
}

@Override
public int size() {
return size;
}

@Override
public int indexOf(E element) {
int index = 0;
while (!p.data.equals(element)) {
index++;
p = p.next;
return -1;
}
}
return index;
}

@Override
public boolean contains(E element) {
return indexOf(element) != -1;
}

@Override
public boolean isEmpty() {
return size == 0 && head == null && tail == null;
}

@Override
public void push(E element) {
}

@Override
public E pop() {
return remove(size - 1);
}

@Override
public E peek() {
return get(size - 1);
}

@Override
public void clear() {
tail = null;
size = 0;
}

@Override
public void sort(Comparator<E> comparator) {
if (comparator == null) {
throw new IllegalArgumentException("comparator can not be null");
}
if (size < 2) {
return;
}
Node j = null;
Node k = null;
E e = null;
e = i.data;
j = i;
k = j.pre;
while (k != tail && comparator.compare(k.data, e) > 0) {
j.data = k.data;
j = j.pre;
k = j.pre;
}
j.data = e;
i = i.next;
}
}

@Override
public List<E> sublist(int fromIndex, int toIndex) {
if (fromIndex < 0 || toIndex >= size || fromIndex >= toIndex) {
throw new IllegalArgumentException("sublist index outof range");
}
for (int i = 0; i < fromIndex; i++) {
nodeA = nodeA.next;
}
for (int i = 0; i < toIndex - 1; i++) {
nodeB = nodeB.next;
}
Node p = nodeA;
while (true) {
if (p == nodeB) {
break;
}
p = p.next;
}
return list;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
if (isEmpty()) {
sb.append(']');
} else {
while (true) {
sb.append(p.data);
if (p == tail) {
sb.append(']');
break;
}
sb.append(',');
p = p.next;
}
}
return sb.toString();
}

@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (obj == this) {
return true;
}
if (this.size == other.size) {
if (this.size == 0) {
return true;
}
while (true) {
if (!p1.data.equals(p2.data)) {
return false;
}
if (p1 == this.tail) {
return true;
}
p1 = p1.next;
p2 = p2.next;
}
} else {
return false;
}
} else {
return false;
}
}

@Override
public Iterator<E> iterator() {
}
private class LinkedListIterator implements Iterator<E> {
private boolean flag = true;
@Override
public boolean hasNext() {
if (isEmpty()) {
return false;
}
return flag;
}

@Override
public E next() {
E ret = cur.data;
cur = cur.next;