我正在尝试使用插入和删除功能创建一个排序的双链表。我已经设法创建了Insert函数,但是我在努力寻找如何删除元素的方法。另外,如果可能的话,我想使用Iterator循环而不是那么多的if循环。归根结底,我要创建一个人员类别(名称和ID),并希望根据其ID对每个人员进行比较/排序。到目前为止,这就是我所拥有的...编辑我设法获得了删除功能,但改用迭代器循环仍然没有运气。
public class SortedDoublyLinkedList<T extends Comparable> {
private Node head = null;
private Node tail = null;
private int count = 0;
class Node {
T value;
Node next;
Node(T value) {
this.value = value;
this.next = next;
}
}
public void insert(T value) {
Node n = new Node(value);
Node prev = null;
Node curr = head;
if (head == null) {
head = n;
tail = n;
} else if (value.compareTo(head.value) < 0) {
n.next = head;
head = n;
} else if (value.compareTo(tail.value) > 0) {
tail.next = n;
tail = n;
} else {
while (value.compareTo(curr.value) > 0) {
prev = curr;
curr = curr.next;
}
prev.next = n;
n.next = curr;
}
count++;
}
public void remove(T value) {
Node temp = head;
Node prev = null;
if (temp != null && temp.value == value) {
head = temp.next;
return;
}
while (temp != null && temp.value != value) {
prev = temp;
temp = temp.next;
}
if (temp == null) {
System.out.println("The value: " + value + " is not in the list!");
return;
}
prev.next = temp.next;
}
public String toString() {
String s = "" + head.value;
Node current = head.next;
while (current != null) {
s += ", " + current.value;
current = current.next;
}
return s;
}
和我的人类...
public class Person {
int ID;
String name;
public Person(int ID, String name) {
this.ID = ID;
this.name = name;
}
public int getID() {return ID;}
public String toString() {
String s = "";
s = s + "ID: " + ID + "\nName: " + name;
return s;
}
}
双向链表的意义在于,每个节点都具有next
指针和previous
指针。这样,您就可以向前和向后遍历链接列表。
鉴于此,从链表中删除一个节点就是在要删除的节点及其旁边的两个节点上重置next
和previous
指针的问题:
node.previous.next = node.next;
node.next.previous = node.previous;
node.next = null;
node.previous = null;
所有要做的就是将删除的节点的上一个和下一个节点链接在一起,从列表中删除该节点。