声明循环双链表类CHDoublelyLinkedList,实现LList接口中的方法。
时间: 2023-06-10 15:06:40 浏览: 102
Double_lin.zip_lin
以下是循环双链表类CHDoublelyLinkedList的实现:
```java
public class CHDoublelyLinkedList<T> implements LList<T> {
private Node<T> head; // 头结点
private int size; // 链表长度
// 内部节点类
private static class Node<T> {
T data; // 数据
Node<T> prev; // 前驱节点
Node<T> next; // 后继节点
Node(T data) {
this.data = data;
}
}
// 构造方法,创建一个空链表
public CHDoublelyLinkedList() {
head = new Node<>(null);
head.prev = head.next = head;
size = 0;
}
// 获取链表长度
@Override
public int size() {
return size;
}
// 判断链表是否为空
@Override
public boolean isEmpty() {
return size == 0;
}
// 获取第index个元素
@Override
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
Node<T> p;
if (index < size / 2) { // 从前往后查找
p = head.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
} else { // 从后往前查找
p = head.prev;
for (int i = size - 1; i > index; i--) {
p = p.prev;
}
}
return p.data;
}
// 设置第index个元素为data
@Override
public void set(int index, T data) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
Node<T> p;
if (index < size / 2) { // 从前往后查找
p = head.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
} else { // 从后往前查找
p = head.prev;
for (int i = size - 1; i > index; i--) {
p = p.prev;
}
}
p.data = data;
}
// 在第index个位置插入元素data
@Override
public void insert(int index, T data) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
Node<T> p;
if (index < size / 2) { // 从前往后查找
p = head.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
} else { // 从后往前查找
p = head.prev;
for (int i = size; i > index; i--) {
p = p.prev;
}
}
Node<T> newNode = new Node<>(data);
newNode.prev = p.prev;
newNode.next = p;
p.prev.next = newNode;
p.prev = newNode;
size++;
}
// 删除第index个元素
@Override
public void delete(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
Node<T> p;
if (index < size / 2) { // 从前往后查找
p = head.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
} else { // 从后往前查找
p = head.prev;
for (int i = size - 1; i > index; i--) {
p = p.prev;
}
}
p.prev.next = p.next;
p.next.prev = p.prev;
size--;
}
}
```
循环双链表类CHDoublelyLinkedList实现了LList接口中的方法,包括获取链表长度、判断链表是否为空、获取第index个元素、设置第index个元素为data、在第index个位置插入元素data和删除第index个元素。其中,get、set、insert和delete方法的时间复杂度为O(n),n为链表长度。
阅读全文