线性表的链式存储与实现
实现线性表的另一种方法是链式存储，即用指针将存储线性表中数据元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在执行插入或 删除运算时，不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间的开销.
单链表
链表是一系列的存储数据元素的单元通过指针串接起来形成的，因此每个单元至少有两个域，一个域用于数据元素的存储，另一个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为结点（node）.
结点接口
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
package com.wjy.Data_Structure.linearlist.common;public interface Node { /** * 获取结点数据域 * * @return */ public Object getData(); /** * 设置结点数据域 * * @param obj */ public void setData(Object obj);} |
单链表结点定义
|
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
|
package com.wjy.Data_Structure.linearlist.common;//单链表结点定义public class SLNode implements Node { private Object element; private SLNode next; public SLNode() { } public SLNode(Object ele, SLNode next) { this.element = ele; this.next = next; } public SLNode getNext() { return next; } public void setNext(SLNode next) { this.next = next; } /******** Methods of Node Interface **********/ @Override public Object getData() { return element; } @Override public void setData(Object obj) { element = obj; }} |
线性表的单链表实现
在使用单链表实现线性表的时候，为了使程序更加简洁，我们通常在单链表的前面添 加一个哑元结点，也称为头结点。在头结点中不存储任何实质的数据对象，其 next 域指向 线性表中 0 号元素所在的结点，头结点的引入可以使线性表运算中的一些边界条件更容易处理。
|
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
package com.wjy.Data_Structure.linearlist.listslinkimpl;import com.wjy.Data_Structure.linearlist.common.DefaultStrategy;import com.wjy.Data_Structure.linearlist.common.List;import com.wjy.Data_Structure.linearlist.common.SLNode;import com.wjy.Data_Structure.linearlist.common.Strategy;import com.wjy.Data_Structure.linearlist.exception.OutOfBoundaryException;//线性表的单链表实现public class ListSLinked implements List { private Strategy strategy; // 数据元素比较策略 private SLNode head; // 单链表首结点引用 private int size;// 线性表中数据元素的个数 public ListSLinked() { this(new DefaultStrategy()); } public ListSLinked(Strategy strategy) { this.strategy = strategy; head = new SLNode(); size = 0; } /** * 辅助方法： 获取数据元素 e 所在结点的前驱结点 * * @param e * @return */ private SLNode getPreNode(Object e) { SLNode p = head; while (p.getNext() != null) if (strategy.equal(p.getNext().getData(), e)) return p; else p = p.getNext(); return null; } /** * 辅助方法： 获取序号为 0<=i<size 的元素所在结点的前驱结点 * * @param i * @return */ private SLNode getPreNode(int i) { SLNode p = head; for (; i > 0; i--) p = p.getNext(); return p; } /** * 辅助方法： 获取序号为 0<=i<size 的元素所在结点 * * @param i * @return */ private SLNode getNode(int i) { SLNode p = head.getNext(); for (; i > 0; i--) p = p.getNext(); return p; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public boolean contains(Object e) { return indexOf(e) != -1; } @Override public int indexOf(Object e) { SLNode p = head.getNext(); int index = 0; while (p != null) if (strategy.equal(p.getData(), e)) { return index; } else { index++; p = p.getNext(); } return -1; } @Override public void insert(int i, Object e) throws OutOfBoundaryException { if (i < 0 || i > size) throw new OutOfBoundaryException("错误，指定的插入序号越界"); SLNode p = getPreNode(i); SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return; } @Override public boolean insertBefore(Object obj, Object e) { SLNode p = getPreNode(obj); if (p != null) { SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return true; } return false; } @Override public boolean insertAfter(Object obj, Object e) { SLNode p = head.getNext(); while (p != null) if (strategy.equal(p.getData(), obj)) { SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return true; } else { p = p.getNext(); } return false; } @Override public Object remove(int i) throws OutOfBoundaryException { if (i < 0 || i >= size) throw new OutOfBoundaryException("错误，指定的删除序号越界。"); SLNode p = getPreNode(i); Object obj = p.getNext().getData(); p.setNext(p.getNext().getNext()); size--; return obj; } @Override public boolean remove(Object e) { SLNode p = getPreNode(e); if (p != null) { p.setNext(p.getNext().getNext()); size--; return true; } return false; } @Override public Object replace(int i, Object e) throws OutOfBoundaryException { if (i < 0 || i >= size) throw new OutOfBoundaryException("错误，指定的序号越界。"); SLNode p = getNode(i); Object obj = p.getData(); p.setData(e); return obj; } @Override public Object get(int i) throws OutOfBoundaryException { if (i < 0 || i >= size) throw new OutOfBoundaryException("错误，指定的序号越界。"); SLNode p = getNode(i); return p.getData(); }} |
简单的测试用例
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
package com.wjy.Data_Structure.linearlist.listslinkimpl;import org.junit.Test;import com.wjy.Data_Structure.linearlist.listslinkimpl.ListSLinked;public class ListSLinkedTest { @Test public void testInsert() { ListSLinked list = new ListSLinked(); for (int i = 0; i < 10; i++) { list.insert(i, i + 1); } System.out.println("删除：" + list.remove(0)); System.out.println(list.contains(1)); list.insertBefore(2, 100); list.insertAfter(2, 101); list.replace(list.getSize() - 1, 1000); for (int i = 0; i < list.getSize(); i++) { System.out.println(list.get(i)); } }} |
数据结构学习代码仓库：
https://git.oschina.net/wjyonlyone/DataStructure
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持服务器之家！
原文链接：http://www.cnblogs.com/Onlywjy/p/6266612.html
