使用java实现双链表,要求包含双链表的主要操作(空置,判断是否为空,表的长度,插入,删除,获取指定位置节点,获取第一元素,获取最后一个元素)
时间: 2024-09-20 22:11:29 浏览: 61
判断表是否为空:表数据为空或者表数据不为空但是有任何一个字段为空都返回0,否则返回1
要实现在Java中创建一个双向链表,你需要定义一个`Node`类来表示链表中的单个节点,以及一个`DoublyLinkedList`类来处理链表的操作。以下是一个简单的实现:
```java
// 定义一个Node类,包含数据和指向前后节点的引用
class Node {
int data;
Node prev;
Node next;
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
// DoublyLinkedList类,包含主要操作的方法
public class DoublyLinkedList {
private Node head;
private Node tail;
private int size;
// 构造器初始化链表为空
public DoublyLinkedList() {
head = null;
tail = null;
size = 0;
}
// 检查链表是否为空
public boolean isEmpty() {
return head == null;
}
// 获取链表的长度
public int length() {
return size;
}
// 插入节点到链表头部
public void insertAtFront(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
size++;
}
// 插入节点到链表尾部
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (tail != null) {
newNode.prev = tail;
tail.next = newNode;
} else {
head = newNode;
tail = newNode;
}
size++;
}
// 删除指定位置的节点,这里假设位置从0开始计数
public void deleteAt(int position) {
if (position < 0 || position >= size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
if (position == 0) {
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
head.prev = null;
}
} else {
Node current = head.next;
for (int i = 0; i < position - 1 && current != null; i++) {
current = current.next;
}
if (current == null) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
current.next = current.next.next;
if (current.next != null) {
current.next.prev = current;
} else {
tail = current;
}
}
size--;
}
// 获取指定位置的节点(如果存在)
public Node get(int position) {
if (position < 0 || position >= size) {
return null;
}
Node current = head;
for (int i = 0; i < position; i++) {
current = current.next;
}
return current;
}
// 获取第一个元素
public int firstElement() {
if (isEmpty()) {
return -1; // 或者抛异常
}
return head.data;
}
// 获取最后一个元素
public int lastElement() {
if (isEmpty()) {
return -1; // 或者抛异常
}
return tail.data;
}
}
```
阅读全文