List容器——LinkedList及常用API，實現棧和隊列，linkedlistapi

List容器——LinkedList及常用API，實現棧和隊列，linkedlistapi

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；

總結：