1.1 basic introduction
The two-way circular linked list is connected end to end based on the two-line linked list (prev of the first node points to the last node, and next of the last node points to the first node).
1.2 add operation
1. Train of thought analysis
Head insertion
When the entire linked list is empty, add operation.
Both the head node and the tail node point to themselves.
Add when the linked list is not empty
First, the previous hop address of the current header node is given to the previous hop of the new element
Then let the trailing pointer of the new node point to the head node, and then let the leading pointer of the head point to the new element.
Update the head node so that the head node points to the new node, and update the tail node so that the next hop of the tail points to the head again.
Tail insertion
Give the next hop of the current tail to the next hop of the new node
Let the next hop of the tail point to the new node, and the previous hop of the new node point to the tail.
tail re points to the new node.
Let the previous jump of the head point to the tail directly.
Middle insertion
1. Closer to the head
Define two pointers p and q, find the node precursor to be inserted, point the previous hop of p to the new node, and point the next hop of the new node to p.
Let the previous hop of q point to the new node and the next hop of the new node point to q.
2. It's close to the tail
Let the next hop of q point to the new node and the previous hop of the new node point to q.
Let the previous hop of p point to the new node and the next hop of the new node point to p.
2. Code example
Linked list class: LinkedList
package cn.linkedlist.demo05;
import java.util.Iterator;
public class LinkedList<E> implements List<E>{
// Create Node
private class Node {
// Data domain
E data;
// Pointer to direct precursor
Node prev;
// Pointer to direct successor
Node next;
// Constructor
public Node() {
this(null, null, null);
}
public Node(E data) {
this(data, null, null);
}
public Node(E data, Node prev, Node next) {
this.data = data;
this.prev = prev;
this.next = next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (prev != null) {
sb.append(prev.data);
} else {
sb.append("null");
}
sb.append("->").append(data).append("->");
if (next != null) {
sb.append(next.data);
} else {
sb.append("null");
}
return sb.toString();
}
}
// Number of linked list elements
private int size;
// Declaration header node
private Node head;
// Declare tail node
private Node tail;
// Initialize header node
public LinkedList() {
head = null;
tail = null;
size = 0;
}
public LinkedList(E[] arr) {
for (E e : arr) {
add(e);
}
}
//Add elements to footer by default
@Override
public void add(E element) {
add(size, element);
}
//Add an element at the specified index in the linked list
@Override
public void add(int index, E element) {
if (index < 0|| index > size) {
throw new ArrayIndexOutOfBoundsException("add index out of bounds");
}
// Create a new node object
Node node = new Node(element);
// The linked list is empty
if(isEmpty()){
head = node;
tail = node;
tail.next = head;
head.prev = tail;
}else if(index == 0){ // Add elements to the head of the linked list
// The previous hop of the head node points to the previous hop of the new node
node.prev = head.prev;
node.next = head;
head.prev = node;
head = node;
tail.next = head;
}else if(index == size){ // Add elements at the end of the linked list
node.next = tail.next;
tail.next = node;
node.prev = tail;
tail = node;
head.prev = tail;
}else{
// Add elements to the linked list
Node p,q; // Define two pointer variables
if(index <= size / 2){
p = head;
for(int i =0; i < index -1 ; i++){
p = p.next;
}
q = p.next;
p.next = node;
node.prev = p;
q.prev = node;
node.next = q;
}else{
p = tail;
for(int i=size -1; i > index; i--){
p = p.prev;
}
q = p.prev;
q.next = node;
node.prev = q;
p.prev = node;
node.next = p;
}
}
size++;
}
@Override
public int size() {
return size;
}
//Find the index of the first occurrence of an element in the linked list
@Override
public int indexOf(E element) {
if(isEmpty()){
return -1;
}
Node p = head;
int index = 0;
while (!p.data.equals(element)){
p = p.next;
index++;
if(p == head){
return -1;
}
}
return index;
}
//Determine whether the element element is included in the linked list
@Override
public boolean contains(E element) {
return indexOf(element) != -1;
}
@Override
public boolean isEmpty() {
return size== 0 && head == null && tail == null;
}
@Override
public void clear() {
head = null;
tail = null;
size = 0;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("size=").append(size).append(", [");
Node node = head;
for (int i = 0; i < size; i++) {
if (i != 0) {
res.append(", ");
}
res.append(node);
node = node.next;
}
res.append("]");
return res.toString();
}
@Override
public Iterator<E> iterator() {
return new DoubleCircleLinkedListIterator();
}
class DoubleCircleLinkedListIterator implements Iterator<E>{
private Node cur = head;
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;
if(cur == head){
flag = false;
}
return ret;
}
}
}
Test class: LinkedListDemo
package cn.linkedlist.demo05;
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
System.out.println("===Linked list header insertion===");
// System.out.println(list);
list.add(0, 1);
list.add(0, 2);
list.add(0, 3);
System.out.println(list);
System.out.println("===Tail insertion of linked list===");
list.add(list.size(), 4);
list.add(list.size(), 5);
list.add(list.size(), 6);
System.out.println(list);
}
}
3. Execution results
1.3 delete
1. Train of thought analysis
Delete header node
The node node is head Next, the final node is the new head node.
The next hop of head is empty.
head jump, node jump.
head's previous jump is empty!! head points to node again.
Finally, let the tail pointer jump to the head again.
Delete tail node
Node is tail Pre precursor, and the final node is the new tail node.
Leave the last jump of tail empty.
The next hop of tail is the next hop of node, and the next hop of tail is empty.
tail re points to node.
The previous jump of head points back to tail.
Delete intermediate node
1. Closer to the head
Define three pointers. p is the precursor of the node to be deleted, q is the node to be deleted, r is the successor of the node to be deleted, and p pointer moves to the precursor of the node to be deleted.
Let the next hop of P point directly to r, and let the previous hop of r point to p again.
Let the previous jump of q and the next jump of q be directly null.
Deletion succeeded.
2. It's close to the tail
Define three node pointers. p is the precursor of the node to be deleted, q is the node to be deleted, and R is the successor of the node to be deleted.
Let the previous jump of R point to p, let the next jump of p point to R, and let both sides of q be empty at the same time!!!
Finally deleted successfully!!!
2. Code example
Linked list class: LinkedList
//Delete the specified element element in the linked list
@Override
public void remove(E element) {
int index = index0f(element);
if(index != -1){
remove(index);
}
}
//Delete the index element at the specified corner mark in the linked list
@Override
public E remove(int index) {
if (index < 0|| index > size) {
throw new ArrayIndexOutOfBoundsException("remove index out of bounds");
}
// Define ret variable
E ret = null;
Node node;
// When there is only one element left in the linked list
if(size ==1){
ret = head.data;
head = null;
tail = null;
// Delete header
}else if(index == 0){
ret = head.data;
node = head.next;
head.next = null;
node.prev = head.prev;
head.prev = null;
head = node;
tail.next = head;
// Delete footer
}else if(index == size -1){
ret = tail.data;
node = tail.prev;
tail.prev = null;
node.next = tail.next;
tail.next = null;
tail = node;
head.prev = tail;
}else{
// Delete an element in the middle of the linked list
Node p, q, r;
if(index <= size / 2){
p = head;
for(int i=0; i < index-1; i++){
p = p.next;
}
q = p.next;
ret = q.data;
r = q.next;
p.next = r;
r.prev = p;
q.next = null;
q.prev = null;
}else{
p = tail;
for(int i = size -1; i > index + 1; i--){
p = p.prev;
}
q = p.prev;
ret = q.data;
r = q.prev;
r.next = p;
p.prev = r;
q.next = null;
q.prev = null;
}
}
size --;
return ret;
}
Test class: LinkedListDemo
package cn.linkedlist.demo05;
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
System.out.println("===Linked list header insertion===");
//System.out.println(list);
list.add(0, 1);
list.add(0, 2);
list.add(0, 3);
System.out.println(list);
System.out.println("===Tail insertion of linked list===");
list.add(list.size(), 4);
list.add(list.size(), 5);
list.add(list.size(), 6);
System.out.println(list);
System.out.println("==Delete element==");
System.out.println(list.remove(3));
System.out.println(list);
}
}
3. Execution results
1.4 modification and acquisition
1. Code example
Linked list class: LinkedList
//Gets the element at the specified index in the linked list
@Override
public E get(int index) {
if (index < 0|| index > size) {
throw new ArrayIndexOutOfBoundsException("get index out of bounds");
}
// Get header
if(index == 0){
return head.data;
}else if(index == size -1){
// Get tail
return tail.data;
}else{
// Get intermediate
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p.data;
}
}
// Modify the element of the index specified in the linked list to element
@Override
public E set(int index, E element) {
if (index < 0|| index > size) {
throw new ArrayIndexOutOfBoundsException("set index out of bounds");
}
E ret = null;
// Get header
if(index == 0){
// Modify header
ret = head.data;
head.data = element;
}else if(index == size -1){
// Modify tail element
ret = tail.data;
tail.data = element;
}else{
// Modify intermediate
Node p = head;
for (int i = 0; i < index; i++) {
p = p.next;
}
ret = p.data;
p.data = element;
}
return ret;
}
Test class: LinkedListDemo
package cn.linkedlist.demo05;
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
System.out.println("===Linked list header insertion===");
//System.out.println(list);
list.add(0, 1);
list.add(0, 2);
list.add(0, 3);
System.out.println(list);
System.out.println("===Tail insertion of linked list===");
list.add(list.size(), 4);
list.add(list.size(), 5);
list.add(list.size(), 6);
System.out.println(list);
System.out.println("==Delete element==");
System.out.println(list.remove(3));
System.out.println(list);
System.out.println("===Update element===");
System.out.println(list.set(2, 66));
System.out.println(list);
System.out.println("===Get element===");
System.out.println(list.get(3));
}
}
2. Execution results
