我有这个作业,我需要为音乐播放器 UI 创建一个双向循环链表。我编写了 addFirst 方法,它工作正常,但是当我创建 addLast 方法时,我似乎无法区分尾部和头部。实际上,我在两种方法中都添加到相同的位置,但不知何故它应该知道一个是新的头,另一个是新的尾。我浏览了互联网,在每个页面中他们基本上都在做同样的事情,所以我被困住了。
class DoublyCircularLinkedList<T> implements IDoublyCircularLinkedList<T> {
//instance variables
private Node<T> current; // The current node in the list
private Node<T> head; // The head node in the list
private int size = 0; // The size of the list
//constructor
public DoublyCircularLinkedList() {
current = null;
head = null;
size = 0;
}
// Adds an element to the head of the list
@Override
public void addFirst(T data) {
if (data instanceof Music) {
Music musicData = (Music) data;
File songFile = new File(musicData.getPath());
if (!songFile.exists()) {
System.out.println("Song file does not exist: " + musicData.getPath());
return; // Stop if the song file doesn't exist
}
}
Node<T> newNode = new Node<>(data);
if (size == 0) {
current = newNode;
head = newNode;
newNode.setNext(newNode);
newNode.setPrev(newNode);
size++;
}
else {
Node<T> tail = head.getPrev();
newNode.setNext(head);//setting new nodes next node to head
head.setPrev(newNode);
newNode.setPrev(tail);
tail.setNext(newNode);
head = newNode;//setting the new node as the head
current = newNode;
size++;
}
}
// Adds an element to the tail of the list
@Override
public void addLast(T data) {
if (data instanceof Music) {
Music musicData = (Music) data;
File songFile = new File(musicData.getPath());
if (!songFile.exists()) {
System.out.println("Song file does not exist: " + musicData.getPath());
return; // Stop if the song file doesn't exist
}
}
Node<T> newNode = new Node<>(data);
if (size == 0) {
current = newNode;
head = newNode;
newNode.setNext(newNode);
newNode.setPrev(newNode);
size++;
}
else {
Node<T> tail = head.getPrev();
newNode.setPrev(tail);
tail.setNext(newNode);
newNode.setNext(head);
head.setPrev(newNode);
current = newNode;
size++;
}
}}
在循环双向链表中,所有元素都是相互链接的,因此无论将元素添加到列表末尾还是列表开头,新元素总是放置在列表的头部和尾部之间。因此,新元素将始终是列表尾部的下一个元素和头部的上一个元素。
private Node<T> createNode(T value) {
Node<T> node = new Node<>();
node.value = value;
node.next = head;
node.prev = tail;
head.prev = node;
tail.next = node;
return node;
}
添加到开头和添加到结尾的区别在于新元素是成为列表的新尾部还是新的头部。如果将一个元素添加到列表的开头,它将成为新的头。如果将新元素添加到列表末尾,它将成为新的尾部。
public void addFirst(T value) {
if (head == null && tail == null) {
head = tail = createList(value);
} else {
head = createNode(value);
}
}
public void addLast(T value) {
if (head == null && tail == null) {
head = tail = createList(value);
} else {
tail = createNode(value);
}
}
剩下的唯一特殊情况是列表仅包含一个元素。在这种情况下,列表的单个元素既是它的头又是它的尾。
private Node<T> createList(T value) {
Node<T> node = new Node<>();
node.value = value;
node.next = node;
node.prev = node;
return node;
}
结果,我们得到以下代码:
public class CircularList<T> implements Iterable<T> {
private Node<T> head;
private Node<T> tail;
public void addFirst(T value) {
if (head == null && tail == null) {
head = tail = createList(value);
} else {
head = createNode(value);
}
}
public void addLast(T value) {
if (head == null && tail == null) {
head = tail = createList(value);
} else {
tail = createNode(value);
}
}
private Node<T> createList(T value) {
Node<T> node = new Node<>();
node.value = value;
node.next = node;
node.prev = node;
return node;
}
private Node<T> createNode(T value) {
Node<T> node = new Node<>();
node.value = value;
node.next = head;
node.prev = tail;
head.prev = node;
tail.next = node;
return node;
}
@Override
public Iterator<T> iterator() {
return new Iterator<T>() {
private Node<T> current;
@Override
public boolean hasNext() {
if (current == null && head != null) {
current = head;
return true;
}
if (current != null && current.next != head) {
current = current.next;
return true;
}
return false;
}
@Override
public T next() {
return current.value;
}
};
}
private static class Node<T> {
private T value;
private Node<T> next;
private Node<T> prev;
}
}