双向就意味着对于每一个元素,都有两个方向的指向
因此从以下几个方面阐述双向链表
- 重要方法分析
- 全部代码
一.重要方法分析
void insert(int key):
int delete():
boolean isEmpty():
二.全部代码
package com.list;
/**
* 双向链表:
* 每两个元素之间都有相互之间的指向
* 前一个元素.next = 下一个元素,下一个元素.prev = 上一个元素
* 但是第一个元素.prev = null ,同理最后一个元素.next = null
*/
public class DoublyLinkedList implements ILinkedList {
LinkedNode head; //这里我们将 head 作为所有节点的头,即 head.next 指向第一个元素
@Override
//将一个节点插入到开头
public void insert(int key) {
LinkedNode node = new LinkedNode(key);
if (!isEmpty()) {
node.next = head.next;
head.next = node;
node.next.prev = node;
} else {
head.next = node;
}
}
@Override
//将末尾的节点删除
public int delete() {
assert !isEmpty();
LinkedNode p = new LinkedNode(0);
p.next = head.next;
while (p.next.next != null) {
p = p.next;
}
//现在 p.next.next 为 null,即 p -> p.next -> null ,现在要删除 p.next
int key = p.next.key;
p.next = null;
return key;
}
@Override
//判空
public boolean isEmpty() {
return head.next == null;
}
public DoublyLinkedList() {
head = new LinkedNode(0);
}
}
