用java声明双链表类DoublyLinkedList,实现LList接口中的方法。
时间: 2023-06-10 13:06:08 浏览: 168
好的,以下是双链表类DoublyLinkedList的声明和实现:
```
public class DoublyLinkedList<T> implements LList<T> {
private Node<T> head;
private Node<T> tail;
private int size;
private static class Node<T> {
T data;
Node<T> next;
Node<T> prev;
Node(T data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
public DoublyLinkedList() {
head = null;
tail = null;
size = 0;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
@Override
public void addFirst(T data) {
Node<T> newNode = new Node<>(data);
if (isEmpty()) {
head = tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
size++;
}
@Override
public void addLast(T data) {
Node<T> newNode = new Node<>(data);
if (isEmpty()) {
head = tail = newNode;
} else {
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
}
size++;
}
@Override
public void add(int index, T data) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Invalid index");
}
if (index == 0) {
addFirst(data);
} else if (index == size) {
addLast(data);
} else {
Node<T> newNode = new Node<>(data);
Node<T> current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
newNode.prev = current.prev;
newNode.next = current;
current.prev.next = newNode;
current.prev = newNode;
size++;
}
}
@Override
public T removeFirst() {
if (isEmpty()) {
throw new NoSuchElementException("List is empty");
}
T data = head.data;
if (head == tail) {
head = tail = null;
} else {
head = head.next;
head.prev = null;
}
size--;
return data;
}
@Override
public T removeLast() {
if (isEmpty()) {
throw new NoSuchElementException("List is empty");
}
T data = tail.data;
if (head == tail) {
head = tail = null;
} else {
tail = tail.prev;
tail.next = null;
}
size--;
return data;
}
@Override
public T remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Invalid index");
}
if (index == 0) {
return removeFirst();
} else if (index == size - 1) {
return removeLast();
} else {
Node<T> current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
T data = current.data;
current.prev.next = current.next;
current.next.prev = current.prev;
size--;
return data;
}
}
@Override
public T getFirst() {
if (isEmpty()) {
throw new NoSuchElementException("List is empty");
}
return head.data;
}
@Override
public T getLast() {
if (isEmpty()) {
throw new NoSuchElementException("List is empty");
}
return tail.data;
}
@Override
public T get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Invalid index");
}
Node<T> current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.data;
}
@Override
public void set(int index, T data) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Invalid index");
}
Node<T> current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
current.data = data;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder("[");
Node<T> current = head;
while (current != null) {
builder.append(current.data);
if (current.next != null) {
builder.append(", ");
}
current = current.next;
}
builder.append("]");
return builder.toString();
}
}
```
上述代码实现了LList接口中的所有方法,同时支持双向遍历。需要注意的是,双链表中的每个节点都有一个指向前一个节点的prev指针和一个指向后一个节点的next指针。
阅读全文