双向链表

单链表中寻找一个已知节点的后继节点,其时间复杂度为O(1),而寻找节点的直接前驱的时间复杂度为O(n),如果要克服单链表的单向性缺点,可以使用双向链表。

节点结构如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Node{
public int item;//数据项
public Node next;//后指针
public Node pre;//前指针

public Node(int item) {
this.item = item;
}

public Node() {
}

public int getItem() {
return item;
}

public void setItem(int item) {
this.item = item;
}

@Override
public String toString() {
return "Node{" +
"item=" + item +
'}';
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public Node getPre() {
return pre;
}

public void setPre(Node pre) {
this.pre = pre;
}


public static void main(String[] args) {
DoubleSinglyLinkedList list = new DoubleSinglyLinkedList();
for (int i = 1; i <= 10; i++) {
list.add(i);
}
list.List();
System.out.println("删除对象为:"+list.delete(3));
list.List();
System.out.println("查询结果为:"+list.Select(3));

}
}
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
public class DoubleSinglyLinkedList {
private Node head;//头部
private Node last;//尾部
private int size;//长度
public DoubleSinglyLinkedList() {
this.head = new Node();
this.last = this.head;
}

public void List(){
Node temp = head.getNext();
for (int i = 0; i < size; i++) {
System.out.println(temp);
temp = temp.getNext();

}
}

public void backList(){//从后往前遍历
Node temp = last;
for (int i = 0; i < size; i++) {
System.out.println(temp);
temp = temp.getPre();
}
}

public void add(int e){
Node node = new Node(e);//实例化节点,并添加元素进去
if (size!=0) node.setPre(last);//指向前一个
last.setNext(node);
last=node;//最后一个节点
size++;
}

public Node delete(int index){
if (index < 0 || index >=size) return null;
if (index == 0){//当索引为0时,删除第一个,把头节点指向第一个节点的指针
Node node = head.getNext();//第一个节点
head.setNext(node.getNext());//设置第二个节点为头节点的指针
node.getNext().setPre(null);
size --;
return node;
}else if (index == size-1){//当索引为0时,删除第一个,把头节点指向第一个节点的指针
Node node = last;
node.getPre().setNext(null);
last = node.getPre();
size --;
return node;
}
Node node = Select(index);
node.getPre().setNext(node.getNext());
node.getNext().setPre(node.getPre());
size--;
return node;
}
public int delete(Node node){
if (!selectNode(node)) return 0;
node.getPre().setNext(node.getNext());
node.getNext().setPre(node.getPre());
size--;
return 1;

}
public Node change(int item,Node node){
if (!selectNode(node)) return null;
node.setItem(item);
return node;
}
public Node change(int item,int index){
if (index <0 || index > size) return null;
Node node = Select(index);
node.setItem(item);
return node;
}

//查
public int getItem(int i){
Node eNode = Select(i);
if (eNode == null) return -1;
return eNode.getItem();
}
//查节点
public Node Select(int i){
if (i < 0 || i >size) return null;
Node node = head;
for (int j=0;j<i;j++)
node = node.getNext();

return node;
}
//查对象
public boolean selectNode(Node n){
Node node = head.getNext();
for (int i = 0; i < size; i++) {
if (node==n) return true;
node = node.getNext();
}
return false;
}

}
测试
1
2
3
4
5
6
7
8
9
10
11
public static void main(String[] args) {
DoubleSinglyLinkedList list = new DoubleSinglyLinkedList();
for (int i = 1; i <= 10; i++) {
list.add(i);
}
list.List();
System.out.println("删除对象为:"+list.delete(3));
list.List();
System.out.println("查询结果为:"+list.Select(3));

}

输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Node{item=1}
Node{item=2}
Node{item=3}
Node{item=4}
Node{item=5}
Node{item=6}
Node{item=7}
Node{item=8}
Node{item=9}
Node{item=10}
删除对象为:Node{item=3}
Node{item=1}
Node{item=2}
Node{item=4}
Node{item=5}
Node{item=6}
Node{item=7}
Node{item=8}
Node{item=9}
Node{item=10}
查询结果为:Node{item=4}