双向链表的创建Java
时间: 2023-09-16 18:06:32 浏览: 69
创建双向链表需要定义一个节点类,节点类中包含三个属性:前驱节点、后继节点和节点值。代码如下:
```
public class ListNode {
int val;
ListNode prev;
ListNode next;
ListNode(int x) { val = x; }
}
```
接下来,我们可以定义一个双向链表类,其中包含头节点和尾节点。代码如下:
```
public class MyLinkedList {
private ListNode head;
private ListNode tail;
private int size;
public MyLinkedList() {
head = null;
tail = null;
size = 0;
}
public int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
ListNode curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr.val;
}
public void addAtHead(int val) {
ListNode newNode = new ListNode(val);
if (size == 0) {
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
size++;
}
public void addAtTail(int val) {
ListNode newNode = new ListNode(val);
if (size == 0) {
head = newNode;
tail = newNode;
} else {
newNode.prev = tail;
tail.next = newNode;
tail = newNode;
}
size++;
}
public void addAtIndex(int index, int val) {
if (index < 0 || index > size) {
return;
}
if (index == 0) {
addAtHead(val);
} else if (index == size) {
addAtTail(val);
} else {
ListNode newNode = new ListNode(val);
ListNode curr = head;
for (int i = 0; i < index - 1; i++) {
curr = curr.next;
}
newNode.prev = curr;
newNode.next = curr.next;
curr.next.prev = newNode;
curr.next = newNode;
size++;
}
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
if (index == 0) {
head = head.next;
if (head == null) {
tail = null;
} else {
head.prev = null;
}
} else if (index == size - 1) {
tail = tail.prev;
tail.next = null;
} else {
ListNode curr = head;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
curr.prev.next = curr.next;
curr.next.prev = curr.prev;
}
size--;
}
}
```
以上代码实现了双向链表的常见操作,包括获取节点值、在链表头部添加节点、在链表尾部添加节点、在指定位置添加节点和删除指定位置的节点。