前言
小朽，晚上回到寝室。烧了开水，又泡了一杯下午喝了的小毛尖。耳机听着萨克斯，总结下今天学的数据结构和算法中的表ADT。
表ADT节点：
#单链表
#双链表
#循环链表
#浅谈面试题一道
喝一口热热的茶，算法和数据结构虽然枯燥，希望我不讲的枯燥。毛尖还是淡淡的味道，非常喜欢。
回顾
①ADT：带一组操作的一些对象的集合：对象及对象的操作。
②java考虑了ADT实现，隐藏了实现的细节。
单链表
①
链表中的数据是以节点来表示的，每个节点的构成：元素(数据元素
的映象) + 指针
(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个节点的地址数据。
上面是比较官方的，我的版本就像老式火车一样：火车节号→火车里面东西
②思考
相比表的数组实现，单链表的好处明显的两点：避免了插入和删除的开销。还有值得说的一点，改变表的起始端（表头和亚节点）。以下是我的观点：如果像一些查询较多的应用，数组和链表都行。但像有些，更新和插入，删除多的情况，比如游戏中的装备等，就应该选择考虑下链表。这就是学这些的nice point。
它冒着热气，像是生活，coding生活那样有味。
③例子来一枚-java
1 package LinkedList;
2
3 /**
4 * <p><strong>我的Java单链表练习</strong></p>
5 * <p>单链表提供了在列表头的高效插入和删除操作，不过在单链表的末尾的插入操作效率很低.</p>
6 * <p>单链表指针域保存着下一节点的引用，尾结点的指针域等于null</p>
7 * @author baby69yy2000
8 */
9 public class SingleLinkedList<T>
{
10
11 /**
12 * 结点类
13 */
14 private static class Node<T>
{
15 T nodeValue;
// 数据域
16 Node<T> next;
// 指针域保存着下一节点的引用
17
18 Node(T nodeValue, Node<T>
next) {
19 this.nodeValue =
nodeValue;
20 this.next =
next;
21 }
22
23 Node(T nodeValue) {
24 this(nodeValue,
null);
25 }
26 }
27
28 // 下面是SingleLinkedList类的数据成员和方法
29 private Node<T>
head, tail;
30
31 public SingleLinkedList() {
32 head = tail =
null;
33 }
34
35 /**
36 * 判断链表是否为空
37 */
38 public boolean isEmpty() {
39 return head ==
null;
40 }
41
42 /**
43 * 创建头指针，该方法只用一次！
44 */
45 public void addToHead(T item) {
46 head =
new Node<T>
(item);
47 if(tail ==
null) tail =
head;
48 }
49
50 /**
51 * 添加尾指针，该方法使用多次
52 */
53 public void addToTail(T item) {
54 if (!isEmpty()) {
// 若链表非空那么将尾指针的next初使化为一个新的元素
55 tail.next =
new Node<T>(item);
// 然后将尾指针指向现在它自己的下一个元素
56 tail =
tail.next;
57 }
else {
// 如果为空则创建一个新的！并将头尾同时指向它
58 head = tail =
new Node<T>
(item);
59 }
60 }
61
62 /**
63 * 打印列表
64 */
65 public void printList() {
66 if (isEmpty()) {
67 System.out.println("null"
);
68 }
else {
69 for(Node<T> p = head; p !=
null; p =
p.next)
70 System.out.println(p.nodeValue);
71 }
72 }
73
74 /**
75 * 在表头插入结点，效率非常高
76 */
77 public void addFirst(T item) {
78 Node<T> newNode =
new Node<T>
(item);
79 newNode.next =
head;
80 head =
newNode;
81 }
82
83 /**
84 * 在表尾插入结点，效率很低
85 */
86 public void addLast(T item) {
87 Node<T> newNode =
new Node<T>
(item);
88 Node<T> p =
head;
89 while (p.next !=
null) p =
p.next;
90 p.next =
newNode;
91 newNode.next =
null;
92 }
93
94 /**
95 * 在表头删除结点，效率非常高
96 */
97 public void removeFirst() {
98 if (!isEmpty()) head =
head.next;
99 else System.out.println("The list have been emptied!"
);
100 }
101
102 /**
103 * 在表尾删除结点，效率很低
104 */
105 public void removeLast() {
106 Node<T> prev =
null, curr =
head;
107 while(curr.next !=
null) {
108 prev =
curr;
109 curr =
curr.next;
110 if(curr.next ==
null) prev.next =
null;
111 }
112 }
113
114 /**
115 * <p>插入一个新结点</p>
116 * <ul>插入操作可能有四种情况:
117 * <li>①表为空, 返回false</li>
118 * <li>②表非空,指定的数据不存在</li>
119 * <li>③指定的数据是表的第一个元素</li>
120 * <li>④指定的数据在表的中间</li></ul>
121 * @param appointedItem 指定的nodeValue
122 * @param item 要插入的结点
123 * @return 成功插入返回true;
124 */
125 public boolean insert(T appointedItem, T item) {
126 Node<T> prev = head, curr =
head.next, newNode;
127 newNode =
new Node<T>
(item);
128 if(!
isEmpty()) {
129 while((curr !=
null) && (!appointedItem.equals(curr.nodeValue))) {
//两个判断条件不能换
130 prev =
curr;
131 curr =
curr.next;
132 }
133 newNode.next = curr;
//②③④
134 prev.next =
newNode;
135 return true;
136 }
137 return false;
//①
138 }
139
140 /**
141 * <p>移除此列表中首次出现的指定元素</p>
142 * <ul>删除操作可能出现的情况:
143 * <li>①prev为空，这意味着curr为head. head = curr.next; --> removeFirst();</li>
144 * <li>②匹配出现在列表中的某个中间位置，此时执行的操作是 --> prev.next = curr.next;,</li></ul>
145 * <p>在列表中定位某个结点需要两个引用:一个对前一结点(prev左)的引用以及一个对当前结点(curr右)的引用.</p>
146 * prev = curr;
147 * curr = curr.next;
148 */
149 public void remove(T item) {
150 Node<T> curr = head, prev =
null;
151 boolean found =
false;
152 while (curr !=
null && !
found) {
153 if (item.equals(curr.nodeValue)) {
154 if(prev ==
null) removeFirst();
155 else prev.next =
curr.next;
156 found =
true;
157 }
else {
158 prev =
curr;
159 curr =
curr.next;
160 }
161 }
162 }
163
164 /**
165 * 返回此列表中首次出现的指定元素的索引，如果列表中不包含此元素，则返回 -1.
166 */
167 public int indexOf(T item) {
168 int index = 0
;
169 Node<T>
p;
170 for(p = head; p !=
null; p =
p.next) {
171 if(item.equals(p.nodeValue))
172 return index;
173 index++
;
174
175 }
176 return -1
;
177 }
178
179 /**
180 * 如果此列表包含指定元素，则返回 true。
181 */
182 public boolean contains(T item) {
183 return indexOf(item) != -1
;
184 }
185
186 public static void main(String[] args) {
187 SingleLinkedList<String> t =
new SingleLinkedList<String>
();
188 t.addToHead("A"
);
189 //t.addFirst("addFirst");
190 t.addToTail("B"
);
191 t.addToTail("C"
);
192 System.out.println(t.indexOf("C"));
// 2
193 System.out.println(t.contains("A"));
// true
194 //t.addLast("addLast");
195 //t.removeLast();
196 //t.insert("B", "insert");
197 //t.removeFirst();
198 //t.remove("B"); // A C
199 t.printList();
// A B C
200
201 }
202
203 }
View Code
双链表
①
双向链表
也叫
双链表
，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从
双向链表
中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
就像火车也升级了，我们一般都用双链表。快捷
②思考
相对单链表，这貌似给我们社会进步意义一样。更容易让我们随心所欲。自然这条路走过了是艰难的。
循环链表
①
循环链表
是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
我认为像小孩子牵着手：童真的我
②思考：像那个经典的约瑟夫问题（有兴趣看看）：
http://baike.baidu.com/link?url=5pqQYc7yv8qBpEbJK3nldHrVfc0rKoOknhm47VNZgi5cnK4uzvzCSCpLsraBtcwo
喝到底了，来块奥利奥加点料。希望你们记住了我说的。
面试题-单链表
快速已知长度的单链表中间节点？
①顺序呗，一个一个走过去。然后知道length，然后知道中间了。大O（N）
②利用二倍，第a个，看看2a，若2a是空，则a为中间。大O（N/2）
总结
不难不难我记住了，喝杯茶继续体会体会。晚安！
转载于:https://www.cnblogs.com/Alandre/p/3592914.html
