9.20打卡带哨兵的双向环形链表

 

 

import java.util.ArrayList;

//双向环形链表 哨兵既是头也是尾 哨兵的prev指向最后一个元素,最后一个元素的next指向哨兵
public class Main {
public static void main(String[] args) {
DoubleLinkedList d = new DoubleLinkedList();
d.addFirst(3);
d.addFirst(2);
d.addFirst(1);
d.addLast(4);
d.addLast(5);
d.addLast(6);
d.addLast(7);
d.removeFirst();
d.removeLast();
d.removeValue(6);
d.insertIndex(0, 1);
d.insertIndex(5, 6);
System.out.println(d.length());
d.removeIndex(1);
d.query();
}

public static class DoubleLinkedList {
public static class Node {
Node prev;
int value;
Node next;

public Node(Node prev, int value, Node next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}

private Node headtail = new Node(null, -1, null);

public DoubleLinkedList() {
headtail.prev = headtail;
headtail.next = headtail;
}

public void addFirst(int value) {

Node p = new Node(headtail, value, headtail.next);
headtail.next.prev = p;
headtail.next = p;

}

public void addLast(int value) {
Node p = new Node(headtail.prev, value, headtail);
headtail.prev.next = p;
headtail.prev = p;
}

public void removeFirst() {
Node p = headtail.next;
if (p.next == p) {
System.out.println("无法删除哨兵");
return;
}
headtail.next = p.next;
p.next.prev = headtail;
}

public void removeLast() {
Node p = headtail.prev;
if (p.next == p) {
System.out.println("无法删除哨兵");
return;
}
p.prev.next = headtail;
headtail.prev = p.prev;
}

public void removeValue(int value) {
ArrayList<Node> nodes = findValue(value);
if (nodes == null || nodes.isEmpty()) {
System.out.println("没有该元素");
return;
}
for (Node node : nodes) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}

public void removeIndex(int index) {
if (index < 0 || index >= length()) {
System.out.println("索引超出范围");
return;
}
if (index == length() - 1) {
removeLast();
return;
}
Node p = findIndex(index);
p.prev.next = p.next;
p.next.prev = p.prev;
}

public void insertIndex(int index, int value) {
Node prev = findIndex(index - 1);
Node p = new Node(prev, value, prev.next);
prev.next.prev = p;//一定注意更改次序
prev.next = p;
}

public ArrayList<Node> findValue(int value) {
ArrayList<Node> nodes = new ArrayList<>();//记录同值节点
for (Node p = headtail.next; p != headtail; p = p.next) {
if (p.value == value) {
nodes.add(p);
}
}
return nodes.isEmpty() ? null : nodes;
}

public Node findIndex(int index) {
if (index == length() - 1) {//最后一个节点
return headtail.prev;
}
int i = -1;
for (Node p = headtail; p.next != headtail; p = p.next) {//要算上哨兵，因为插入需要找前第一个节点，但最后一个节点无法找到
if (i == index) {
return p;
}
i++;
}
return null;
}

public int length() {
int i = 0;
for (Node p = headtail.next; p != headtail; p = p.next) {
i++;
}
return i;
}

public void query() {
for (Node p = headtail.next; p != headtail; p = p.next) {//不输出哨兵
System.out.print(p.value + " ");
}
}
}
}