要实现一个有序双向链表,可以按照以下步骤进行:
class Node {
Node prev;
int value;
Node next;
}
class SortedDoublyLinkedList {
Node head;
Node tail;
}
void insert(int value) {
Node newNode = new Node();
newNode.value = value;
if (head == null) {
head = newNode;
tail = newNode;
} else {
Node current = head;
while (current != null && current.value < value) {
current = current.next;
}
if (current == head) {
newNode.next = head;
head.prev = newNode;
head = newNode;
} else if (current == null) {
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
} else {
newNode.prev = current.prev;
newNode.next = current;
current.prev.next = newNode;
current.prev = newNode;
}
}
}
void remove(int value) {
if (head == null) {
return;
}
Node current = head;
while (current != null && current.value != value) {
current = current.next;
}
if (current == head) {
head = head.next;
if (head != null) {
head.prev = null;
} else {
tail = null;
}
} else if (current == tail) {
tail = tail.prev;
tail.next = null;
} else {
current.prev.next = current.next;
current.next.prev = current.prev;
}
}
这样就可以实现一个基本的有序双向链表,在插入和删除节点时能够保持链表的有序性。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
推荐阅读:java双向链表怎么实现