双向链表是一个基本的数据结构,在Java中LinkedList已经实现了这种结构,不过作为开发者,也要拥有自己显示这种结构的能力。话不多说,上代码:
首先是链表的节点类:
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
|
/** * 链表节点 * @author Administrator * * @param <T> */ public class ChainNode<T> { private T data; //对象编号 private int dataNo; public ChainNode<T> nextChainNode; public ChainNode<T> preChainNode; public ChainNode(T data, ChainNode<T> nextChainNode, ChainNode<T> preChainNode) { this .data = data; this .nextChainNode = nextChainNode; this .preChainNode = preChainNode; } public ChainNode(T data) { this .data = data; } public int getDataNo() { return dataNo; } public void setDataNo( int dataNo) { this .dataNo = dataNo; } public void setData(T data) { this .data = data; } public T getData() { return data; } } |
然后是链表:
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
|
<pre name= "code" class = "java" > /** * 链表实现类 * @author Administrator * * @param <T> */ public class Chain<T> { //头节点 private ChainNode<T> headNode; //末尾节点指针 private ChainNode<T> lastNode; private int size; //创建链表就创建头节点 public Chain() { this .headNode = new ChainNode<T>( null ); this .lastNode = headNode; } //增加一个节点 public void addNode(T data) { ChainNode<T> node = new ChainNode<T>(data); if (lastNode != null ){ lastNode.nextChainNode = node; node.preChainNode = node; node.setDataNo(size); lastNode = node; size++; } } //删除指定索引的节点 public void deleteNode( int dataNo) throws Exception { if (getSize() == 0 ){ throw new Exception( "chain is empty" ); } for (ChainNode<T> node = headNode.nextChainNode;node != null ;node = node.nextChainNode) { if (node.getDataNo() == dataNo){ node.preChainNode.nextChainNode = node.nextChainNode; if (node.nextChainNode != null ){ node.nextChainNode.preChainNode = node.preChainNode; } node.nextChainNode = null ; node.preChainNode = null ; size--; //重新设置节点的编号 for (ChainNode<T> chainNode = node.nextChainNode;chainNode != null ;chainNode = chainNode.nextChainNode) { chainNode.setDataNo(chainNode.getDataNo()- 1 ); } return ; } } throw new Exception( "the corresponding data that can not be found" ); } //获取指定索引的节点 public T get( int dataNo) throws Exception { if (getSize() == 0 ){ throw new Exception( "chain is empty" ); } for (ChainNode<T> node = headNode.nextChainNode;node != null ;node = node.nextChainNode) { if (node.getDataNo() == dataNo){ return node.getData(); } } throw new Exception( "the corresponding data that can not be found" ); } //修改对应索引的节点 public void set( int dataNo,T data) throws Exception { if (getSize() == 0 ){ throw new Exception( "chain is empty" ); } for (ChainNode<T> node = headNode.nextChainNode;node != null ;node = node.nextChainNode) { if (node.getDataNo() == dataNo){ node.setData(data); return ; } } throw new Exception( "the data that is to be modified can not be found" ); } //是否包含对应数据的节点 public boolean isContains(T data) throws Exception { if (getSize() == 0 ){ throw new Exception( "chain is empty" ); } for (ChainNode<T> chainNode = headNode.nextChainNode;chainNode != null ;chainNode = chainNode.nextChainNode) { if (chainNode.getData() == data){ return true ; } } return false ; } //获取节点数量(不含头节点) public int getSize() { return size; } } |
测试一下:
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
|
public class ChainTest { public static void main(String[] args) throws Exception{ String oneString = "one" ; String twoString = "two" ; String threeString = "three" ; String fourString = "four" ; Chain<String> chain = new Chain<String>(); chain.addNode(oneString); chain.addNode(twoString); chain.addNode(threeString); chain.addNode(fourString); for ( int i = 0 ; i < chain.getSize(); i++) { String string2 = chain.get(i); System.out.println(string2); } try { String string = chain.get( 2 ); System.out.println( "the data of the second node is" +string); System.out.println(chain.isContains(fourString)); chain.set( 1 , "haha" ); System.out.println( "modify chain" ); for ( int i = 0 ; i < chain.getSize(); i++) { String string2 = chain.get(i); System.out.println(string2); } chain.deleteNode( 3 ); System.out.println( "delete one node" ); for ( int i = 0 ; i < chain.getSize(); i++) { String string2 = chain.get(i); System.out.println(string2); } } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } } } |
结果:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
one two three four the data of the second node isthree true modify chain one haha three four delete one node one haha three |
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
原文链接:http://blog.csdn.net/sinat_23092639/article/details/51160621