链表实现与时间复杂度分析

一、链表：

二、链表的两种实现：

1.不适用虚拟头节点

　　不用虚拟头节点在添加元素的操作上要单独考虑在链表的头添加元素。而加了虚拟头节点可以统一处理，关键是要找到要添加节点的前一个节点

 1 public class LinkedList<E> {
 2 
 3     private class Node{
 4         public E e;
 5         public Node next;
 6 
 7         public Node(E e, Node next){
 8             this.e = e;
 9             this.next = next;
10         }
11 
12         public Node(E e){
13             this(e, null);
14         }
15 
16         public Node(){
17             this(null, null);
18         }
19 
20         @Override
21         public String toString(){
22             return e.toString();
23         }
24     }
25 
26     private Node head;
27     private int size;
28 
29     public LinkedList(){
30         head = null;
31         size = 0;
32     }
33 
34     // 获取链表中的元素个数
35     public int getSize(){
36         return size;
37     }
38 
39     // 返回链表是否为空
40     public boolean isEmpty(){
41         return size == 0;
42     }
43 
44     // 在链表头添加新的元素e
45     public void addFirst(E e){
46 //        Node node = new Node(e);
47 //        node.next = head;
48 //        head = node;
49 
50         head = new Node(e, head);
51         size ++;
52     }
53 
54     // 在链表的index(0-based)位置添加新的元素e
55     // 在链表中不是一个常用的操作，练习用：）
56     public void add(int index, E e){
57 
58         if(index < 0 || index > size)
59             throw new IllegalArgumentException("Add failed. Illegal index.");
60 
61         if(index == 0)
62             addFirst(e);
63         else{
64             Node prev = head;
65             for(int i = 0 ; i < index - 1 ; i ++)
66                 prev = prev.next;
67 
68 //            Node node = new Node(e);
69 //            node.next = prev.next;
70 //            prev.next = node;
71 
72             prev.next = new Node(e, prev.next);
73             size ++;
74         }
75     }
76 
77     // 在链表末尾添加新的元素e
78     public void addLast(E e){
79         add(size, e);
80     }
81 }

2.使用虚拟头节点

（今后所有的链表操作都使用虚拟头节点）

  1 public class LinkedList<E> {
  2 
  3     private class Node{
  4         public E e;
  5         public Node next;
  6 
  7         public Node(E e, Node next){
  8             this.e = e;
  9             this.next = next;
 10         }
 11 
 12         public Node(E e){
 13             this(e, null);
 14         }
 15 
 16         public Node(){
 17             this(null, null);
 18         }
 19 
 20         @Override
 21         public String toString(){
 22             return e.toString();
 23         }
 24     }
 25 
 26     private Node dummyHead;
 27     private int size;
 28 
 29     public LinkedList(){
 30         dummyHead = new Node();
 31         size = 0;
 32     }
 33 
 34     // 获取链表中的元素个数
 35     public int getSize(){
 36         return size;
 37     }
 38 
 39     // 返回链表是否为空
 40     public boolean isEmpty(){
 41         return size == 0;
 42     }
 43 
 44     // 在链表的index(0-based)位置添加新的元素e
 45     // 在链表中不是一个常用的操作，练习用：）
 46     public void add(int index, E e){
 47 
 48         if(index < 0 || index > size)
 49             throw new IllegalArgumentException("Add failed. Illegal index.");
 50 
 51         Node prev = dummyHead;
 52         for(int i = 0 ; i < index ; i ++)
 53             prev = prev.next;
 54 
 55         prev.next = new Node(e, prev.next);
 56         size ++;
 57     }
 58 
 59     // 在链表头添加新的元素e
 60     public void addFirst(E e){
 61         add(0, e);
 62     }
 63 
 64     // 在链表末尾添加新的元素e
 65     public void addLast(E e){
 66         add(size, e);
 67     }
 68 
 69     // 获得链表的第index(0-based)个位置的元素
 70     // 在链表中不是一个常用的操作，练习用：）
 71     public E get(int index){
 72 
 73         if(index < 0 || index >= size)
 74             throw new IllegalArgumentException("Get failed. Illegal index.");
 75 
 76         Node cur = dummyHead.next;
 77         for(int i = 0 ; i < index ; i ++)
 78             cur = cur.next;
 79         return cur.e;
 80     }
 81 
 82     // 获得链表的第一个元素
 83     public E getFirst(){
 84         return get(0);
 85     }
 86 
 87     // 获得链表的最后一个元素
 88     public E getLast(){
 89         return get(size - 1);
 90     }
 91 
 92     // 修改链表的第index(0-based)个位置的元素为e
 93     // 在链表中不是一个常用的操作，练习用：）
 94     public void set(int index, E e){
 95         if(index < 0 || index >= size)
 96             throw new IllegalArgumentException("Set failed. Illegal index.");
 97 
 98         Node cur = dummyHead.next;
 99         for(int i = 0 ; i < index ; i ++)
100             cur = cur.next;
101         cur.e = e;
102     }
103 
104     // 查找链表中是否有元素e
105     public boolean contains(E e){
106         Node cur = dummyHead.next;
107         while(cur != null){
108             if(cur.e.equals(e))
109                 return true;
110             cur = cur.next;
111         }
112         return false;
113     }
114 
115     @Override
116     public String toString(){
117         StringBuilder res = new StringBuilder();
118 
119 //        Node cur = dummyHead.next;
120 //        while(cur != null){
121 //            res.append(cur + "->");
122 //            cur = cur.next;
123 //        }
124         for(Node cur = dummyHead.next ; cur != null ; cur = cur.next)
125             res.append(cur + "->");
126         res.append("NULL");
127 
128         return res.toString();
129     }
130 }

三、链表的增、删、查、改、遍历

  1 public class LinkedList<E> {
  2 
  3     private class Node{
  4         public E e;
  5         public Node next;
  6 
  7         public Node(E e, Node next){
  8             this.e = e;
  9             this.next = next;
 10         }
 11 
 12         public Node(E e){
 13             this(e, null);
 14         }
 15 
 16         public Node(){
 17             this(null, null);
 18         }
 19 
 20         @Override
 21         public String toString(){
 22             return e.toString();
 23         }
 24     }
 25 
 26     private Node dummyHead;
 27     private int size;
 28 
 29     public LinkedList(){
 30         dummyHead = new Node();
 31         size = 0;
 32     }
 33 
 34     // 获取链表中的元素个数
 35     public int getSize(){
 36         return size;
 37     }
 38 
 39     // 返回链表是否为空
 40     public boolean isEmpty(){
 41         return size == 0;
 42     }
 43 
 44     // 在链表的index(0-based)位置添加新的元素e
 45     // 在链表中不是一个常用的操作，练习用：）
 46     public void add(int index, E e){
 47 
 48         if(index < 0 || index > size)
 49             throw new IllegalArgumentException("Add failed. Illegal index.");
 50 
 51         Node prev = dummyHead;
 52         for(int i = 0 ; i < index ; i ++)
 53             prev = prev.next;
 54 
 55         prev.next = new Node(e, prev.next);
 56         size ++;
 57     }
 58 
 59     // 在链表头添加新的元素e
 60     public void addFirst(E e){
 61         add(0, e);
 62     }
 63 
 64     // 在链表末尾添加新的元素e
 65     public void addLast(E e){
 66         add(size, e);
 67     }
 68 
 69     // 获得链表的第index(0-based)个位置的元素
 70     // 在链表中不是一个常用的操作，练习用：）
 71     public E get(int index){
 72 
 73         if(index < 0 || index >= size)
 74             throw new IllegalArgumentException("Get failed. Illegal index.");
 75 
 76         Node cur = dummyHead.next;
 77         for(int i = 0 ; i < index ; i ++)
 78             cur = cur.next;
 79         return cur.e;
 80     }
 81 
 82     // 获得链表的第一个元素
 83     public E getFirst(){
 84         return get(0);
 85     }
 86 
 87     // 获得链表的最后一个元素
 88     public E getLast(){
 89         return get(size - 1);
 90     }
 91 
 92     // 修改链表的第index(0-based)个位置的元素为e
 93     // 在链表中不是一个常用的操作，练习用：）
 94     public void set(int index, E e){
 95         if(index < 0 || index >= size)
 96             throw new IllegalArgumentException("Set failed. Illegal index.");
 97 
 98         Node cur = dummyHead.next;
 99         for(int i = 0 ; i < index ; i ++)
100             cur = cur.next;
101         cur.e = e;
102     }
103 
104     // 查找链表中是否有元素e
105     public boolean contains(E e){
106         Node cur = dummyHead.next;
107         while(cur != null){
108             if(cur.e.equals(e))
109                 return true;
110             cur = cur.next;
111         }
112         return false;
113     }
114 
115     // 从链表中删除index(0-based)位置的元素, 返回删除的元素
116     // 在链表中不是一个常用的操作，练习用：）
117     public E remove(int index){
118         if(index < 0 || index >= size)
119             throw new IllegalArgumentException("Remove failed. Index is illegal.");
120 
121         Node prev = dummyHead;
122         for(int i = 0 ; i < index ; i ++)
123             prev = prev.next;
124 
125         Node retNode = prev.next;
126         prev.next = retNode.next;
127         retNode.next = null;
128         size --;
129 
130         return retNode.e;
131     }
132 
133     // 从链表中删除第一个元素, 返回删除的元素
134     public E removeFirst(){
135         return remove(0);
136     }
137 
138     // 从链表中删除最后一个元素, 返回删除的元素
139     public E removeLast(){
140         return remove(size - 1);
141     }
142 
143     // 从链表中删除元素e
144     public void removeElement(E e){
145 
146         Node prev = dummyHead;
147         while(prev.next != null){
148             if(prev.next.e.equals(e))
149                 break;
150             prev = prev.next;
151         }
152 
153         if(prev.next != null){
154             Node delNode = prev.next;
155             prev.next = delNode.next;
156             delNode.next = null;
157             size --;
158         }
159     }
160 
161     @Override
162     public String toString(){
163         StringBuilder res = new StringBuilder();
164 
165         Node cur = dummyHead.next;
166         while(cur != null){
167             res.append(cur + "->");
168             cur = cur.next;
169         }
170         res.append("NULL");
171 
172         return res.toString();
173     }
174 }

四、时间复杂度分析