双向链表
上次说到了单向链表 , 我么可以很轻松的从一个元素获取到下一个元素的引用 , 但是 , 如果我们突然有一个要获取上一个元素的需求呢 ? 这相对来说就很难了 , 尽管你可以在使用的时候专门创建一个对变量来指向上一个元素 .
双向链表的节点元素
双向链表的节点其实和单向链表差不多 , 只不过还要添加一个属性来引用最后一个元素 .
private class Node {
public Item item = null;//元素节点内容
public Node next = null;//下一个节点的引用
public Node prev = null;//上一个节点的引用
public Node(Item item) {
this.item = item;
}
}
方法列表
-
add(Item item)
: 添加一个新元素节点 . -
remove(int index)
: 根据索引删除一个元素节点 . -
remove(Item item)
: 根据给定得Item
对象 , 删除一个元素节点 . -
toString()
: 正向遍历输出所有元素节点 . -
reverseToString()
: 反向遍历输出所有元素节点 .
代码实现
因为和单向链表差不多 , 只是对于
prev
要稍作处理 , 所以接不多说了 .
public class DoubleLinkList<Item> {
/**
* length : 链表长度
* head : 链表第一个节点
* tail : 链表最后一个节点
*/
private int length = 0;
private Node head = null;
private Node tail = null;
public void add(Item item) {
Node newNode = new Node(item);
if (this.length == 0) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.length++;
}
public boolean remove(int index) {
if (index < 0 || index > this.length) {
return false;
}
Node current = this.head;
int i = 0;
while (i <= index) {
current = current.next;
}
current.prev.next = current.next;
current.next.prev = current.prev;
this.length--;
return true;
}
public boolean remove(Item item) {
Node current = this.head;
while (current.item != item) {
current = current.next;
if (current == null) {
return false;
}
}
current.prev.next = current.next;
current.next.prev = current.prev;
this.length--;
return true;
}
public String toString() {
String str = "";
Node current = this.head;
str += current.item;
while (current.next != null) {
current = current.next;
str += current.item;
}
return str;
}
public String reverseToString() {
String str = "";
Node current = this.tail;
str += current.item;
while (current.prev != null) {
current = current.prev;
str += current.item;
}
return str;
}
private class Node {
public Item item = null;
public Node next = null;
public Node prev = null;
public Node(Item item) {
this.item = item;
}
}
}