用java写个双向链表
时间: 2024-02-28 14:28:30 浏览: 12
以下是一个简单的双向链表的Java实现:
```java
public class DoublyLinkedList<T> {
private Node<T> head;
private Node<T> tail;
private int size;
private static class Node<T> {
T data;
Node<T> prev;
Node<T> next;
Node(T data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
public DoublyLinkedList() {
head = null;
tail = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public T getFirst() {
if (isEmpty()) {
throw new RuntimeException("List is empty");
}
return head.data;
}
public T getLast() {
if (isEmpty()) {
throw new RuntimeException("List is empty");
}
return tail.data;
}
public void addFirst(T data) {
Node<T> newNode = new Node<>(data);
if (isEmpty()) {
tail = newNode;
} else {
head.prev = newNode;
}
newNode.next = head;
head = newNode;
size++;
}
public void addLast(T data) {
Node<T> newNode = new Node<>(data);
if (isEmpty()) {
head = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
}
tail = newNode;
size++;
}
public T removeFirst() {
if (isEmpty()) {
throw new RuntimeException("List is empty");
}
T data = head.data;
head = head.next;
size--;
if (isEmpty()) {
tail = null;
} else {
head.prev = null;
}
return data;
}
public T removeLast() {
if (isEmpty()) {
throw new RuntimeException("List is empty");
}
T data = tail.data;
tail = tail.prev;
size--;
if (isEmpty()) {
head = null;
} else {
tail.next = null;
}
return data;
}
}
```
这个实现包含一个嵌套的Node类,用于存储每个元素的数据和前驱和后继节点。DoublyLinkedList类包含头部和尾部节点的引用,以及一个size变量用于跟踪列表的大小。实现了许多常见的双向链表操作,如添加、删除和访问元素的方法。