LinkedList及常用API ① LinkedList 鏈表 ② LinkedList類擴展AbstractSequentialList並實現List介面 ③ LinkedList提供了一個鏈表數據結構 ④ LinkedList有兩個構造方法 a) LinkedList() b) LinkedL ...
LinkedList及常用API
① LinkedList----鏈表
② LinkedList類擴展AbstractSequentialList並實現List介面
③ LinkedList提供了一個鏈表數據結構
④ LinkedList有兩個構造方法
a) LinkedList()
b) LinkedList(Collection c)
⑤ 除了繼承的方法之外，LinkedList類還定義了一些有用的方法用於操作和訪問容器中的數據;
a) void addFirst(E e)
b) void addLast(E e)
c) E removeFirst()
d) E removeLast()
1 LinkedList<String> sList = new LinkedList<String>();
2 sList.add("zhangsan");// 將指定元素添加到此列表的結尾
3 sList.add("lisi");
4 sList.add("wangwu");
5 sList.add("rose");
6 sList.add("mary");
7 sList.add("jack");
8 sList.addFirst("jay");// 將指定元素插入此列表的開頭
9 sList.addLast("jhon");// 將指定元素添加到此列表的結尾
10 for (String name : sList) {
11 System.out.println(name);
12 }
13
14 System.out.println("****************************************");
15 System.out.println(sList.removeFirst());//移除並返回此列表的第一個元素;如果此列表為空，NoSuchElementException
16 sList.clear();
17 System.out.println(sList.size());//返回此列表的元素數
18 System.out.println(sList.pollFirst());//獲取並移除此列表的第一個元素；如果此列表為空，則返回 null
Linked中鏈表結構如下：
LinkedList中的 remove(Object)方法如下：
1 public boolean remove(Object o) {
2 if (o == null) {
3 for (Node<E> x = first; x != null; x = x.next) {
4 if (x.item == null) {
5 unlink(x);
6 return true;
7 }
8 }
9 } else {
10 for (Node<E> x = first; x != null; x = x.next) {
11 if (o.equals(x.item)) {
12 unlink(x);
13 return true;
14 }
15 }
16 }
17 return false;
18 }
再找到unlink方法
1 E unlink(Node<E> x) {
2 // assert x != null;
3 final E element = x.item;
4 final Node<E> next = x.next;
5 final Node<E> prev = x.prev;
6
7 if (prev == null) {
8 first = next;
9 } else {
10 prev.next = next;
11 x.prev = null;
12 }
13
14 if (next == null) {
15 last = prev;
16 } else {
17 next.prev = prev;
18 x.next = null;
19 }
20
21 x.item = null;
22 size--;
23 modCount++;
24 return element;
25 }
從中可以看到刪除時做的操作是，將要刪除的元素b設為null，並且將其上一個元素a指向b的下一個元素c，將c指向a；
總結：
內部封裝的是雙向鏈表數據結構
每個節點是一個Node對象，Node對象中封裝的是你要添加的元素
還有一個指向上一個Node對象的引用和指向下一個Node對象的引用
不同的容器有不同的數據結構，不同的數據結構操作起來性能是不同的
鏈表數據結構，做插入，刪除的效率比較高，但查詢效率比較低
數組結構，它做查詢的效率高，因為可以通過下標直接找到元素
但插入刪除效率比較低，因為要做移位操作
二：用LinkedList實現棧和隊列
棧的特點，後進先出
棧的方法：
1 class MyStack<T>{
2 private LinkedList<T> data=null;
3 public MyStack() {
4 data=new LinkedList<T>();
5 }
6
7 //壓棧的方法
8 public void push(T obj) {
9 data.addFirst(obj);
10 }
11
12 public T pop() {
13 return data.removeFirst();
14 }
15
16 public Iterator<T> iterator() {
17 return data.iterator();
18 }
19 }
main函數中添加及使用：
1 MyStack<String> mystack=new MyStack<String>();
2 mystack.push("zhangsan");
3 mystack.push("lisi");
4 mystack.push("wangwu");
5 mystack.push("zhaoliu");
6 mystack.pop();
7 mystack.pop();
8 Iterator<String> it=mystack.iterator();
9 while(it.hasNext()){
10 System.out.println(it.next());
11 }
輸出結果：
lisi
zhangsan
隊列的特點：先進先出
隊列的方法：
1 class myQueue<T>{
2 private LinkedList<T> data=null;
3 public myQueue(){
4 data=new LinkedList<T>();
5 }
6
7 public void push(T obj) {
8 data.addFirst(obj);
9 }
10
11 public T pop() {
12 return data.removeLast();
13 }
14
15 public Iterator<T> iterotor() {
16 return data.iterator();
17 }
18 }
main函數中添加及使用：
1 myQueue<Integer> myQueue=new myQueue<Integer>();
2 myQueue.push(1);
3 myQueue.push(2);
4 myQueue.push(3);
5 myQueue.push(4);
6 myQueue.push(5);
7 myQueue.pop();
8 myQueue.pop();
9 Iterator<Integer> it= myQueue.iterotor();
10 while (it.hasNext()) {
11 System.out.println(it.next());
12 }
輸出結果：
5
4
3
