java声明循环单链表类CircSinglyLinkedList,实现LList接口中的方法的代码
时间: 2023-06-13 17:04:17 浏览: 175
Java单链表的实现代码
以下是Java代码实现:
```java
public class CircSinglyLinkedList<E> implements LList<E> {
private Node<E> tail;
private int size;
public CircSinglyLinkedList() {
tail = null;
size = 0;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
@Override
public boolean add(int index, E element) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index out of range: " + index);
}
Node<E> newNode = new Node<>(element);
if (isEmpty()) {
tail = newNode;
tail.next = tail;
} else if (index == 0) {
newNode.next = tail.next;
tail.next = newNode;
} else if (index == size) {
newNode.next = tail.next;
tail.next = newNode;
tail = newNode;
} else {
Node<E> prev = getNode(index - 1);
newNode.next = prev.next;
prev.next = newNode;
}
size++;
return true;
}
@Override
public boolean add(E element) {
return add(size, element);
}
@Override
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of range: " + index);
}
E removedElement;
if (size == 1) {
removedElement = tail.element;
tail = null;
} else if (index == 0) {
removedElement = tail.next.element;
tail.next = tail.next.next;
} else if (index == size - 1) {
Node<E> prev = getNode(index - 1);
removedElement = tail.element;
prev.next = tail.next;
tail = prev;
} else {
Node<E> prev = getNode(index - 1);
removedElement = prev.next.element;
prev.next = prev.next.next;
}
size--;
return removedElement;
}
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of range: " + index);
}
Node<E> node = getNode(index);
return node.element;
}
@Override
public int indexOf(E element) {
if (isEmpty()) {
return -1;
}
int index = 0;
Node<E> node = tail.next;
do {
if (Objects.equals(element, node.element)) {
return index;
}
node = node.next;
index++;
} while (node != tail.next);
return -1;
}
@Override
public E set(int index, E element) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index out of range: " + index);
}
Node<E> node = getNode(index);
E replacedElement = node.element;
node.element = element;
return replacedElement;
}
private Node<E> getNode(int index) {
if (index == size - 1) {
return tail;
}
Node<E> node = tail.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
private static class Node<E> {
E element;
Node<E> next;
Node(E element) {
this.element = element;
}
}
}
```
上述代码中,我们实现了循环单链表类 `CircSinglyLinkedList<E>`,并实现了 `LList<E>` 接口中的方法。其中,我们使用了一个内部类 `Node<E>` 表示节点,每个节点包含一个元素和一个指向下一个节点的引用。类 `CircSinglyLinkedList<E>` 中的 `tail` 属性指向最后一个节点,因为这是循环单链表的特殊之处。通过这个属性,我们可以方便地实现在尾部添加元素和删除最后一个元素的方法。
阅读全文