4.4 链表元素 get、set、是否存在操作
//在链表的index(0-based)位置添加新的元素e public E get(int index){ if(index < 0 || index > size) throw new IllegalArgumentException("Get failed. Illegal index."); Node cur = dummyHead.next; for (int i = 0; i < index; i++) cur = cur.next; return cur.e; } //获得链表的第一个元素 public E getFirst(){ return get(0); } //获取链表的最后一个元素 public E getLast(){ return get(size - 1); } //在链表的index(0-based)位置添加新的元素e public void set(int index,E e){ if(index < 0 || index > size) throw new IllegalArgumentException("Set failed. Illegal index."); Node cur = dummyHead.next; for (int i = 0; i < index; i++) cur = cur.next; cur.e = e; } //查找链表中是否有元素e public boolean contains(E e){ Node cur = dummyHead.next; while (cur != null){ if(cur.e.equals(e)) return true; cur = cur.next; } return false; }
4.5.1 修改和查找操作时间复杂度
| 功能 | 时间复杂度 |
| set(index,e) | O(n) |
| get(index) | O(n) |
| contains(e) | O(n) |
4.5 删除链表元素
加入我们想要删除索引为 (2) 位置的元素，我们需要找到 待删除节点之前的一个位置，也就是(1) ，我们用 prev 表示，找到这个节点之后，那么 (2) 就是我们需要删除的索引了 我们叫 delNode，如下图所示：
代码实现：
//从链表中删除Index(0-based)位置的元素，返回删除的元素 public E remove(int index){ if(index < 0 || index > size) throw new IllegalArgumentException("Remove failed. Illegal index."); Node prev = dummyHead; for (int i = 0; i < index; i++) prev = prev.next; Node retNode = prev.next; prev.next = retNode.next; retNode.next = null; size --; return retNode.e; } //从链表中删除第一个位置的元素 public E removeFirst(){ return remove(0); } //从链表中删除最后一个位置的元素 public E removeLast(){ return remove(size - 1); }
4.5.1 删除操作时间复杂度
| 功能 | 时间复杂度 |
| removeList(e) | O(n) |
| removeFirst(e) | O(1) |
| remove(index,e) | O(n/2) = O(n) |
4.6 完整代码
/** * 底层链表的内部类 * @param <E> */ public class LinkedList<E> { private class Node{ public E e; public Node next;//public 可以在LinkedList随意操作 public Node(E e,Node next){ this.e = e; this.next = next; } public Node(E e){ this(e,null); } public Node(){ this(null,null); } @Override public String toString() { return e.toString(); } } private Node dummyHead; int size; public LinkedList(){ dummyHead = new Node(null,null); size = 0; } //获取链表中的元素个数 public int getSize(){ return size; } //返回链表是否为空 public boolean isEmpty(){ return size == 0; } //在链表头中添加元素e public void addFirst(E e){ //方式一 // Node node = new Node(e); // node.next = head; // head = node; //方式二 add(0,e); } //在链表的index(0-based)位置添加新的元素e public void add(int index,E e){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed. Illegal index."); Node prev = dummyHead; for (int i = 0; i < index; i++) prev = prev.next; prev.next = new Node(e,prev.next); size ++; } //在链表末尾添加新的元素e public void addLast(E e){ add(size,e); } //在链表的index(0-based)位置添加新的元素e public E get(int index){ if(index < 0 || index > size) throw new IllegalArgumentException("Get failed. Illegal index."); Node cur = dummyHead.next; for (int i = 0; i < index; i++) cur = cur.next; return cur.e; } //获得链表的第一个元素 public E getFirst(){ return get(0); } //获取链表的最后一个元素 public E getLast(){ return get(size - 1); } //在链表的index(0-based)位置添加新的元素e public void set(int index,E e){ if(index < 0 || index > size) throw new IllegalArgumentException("Set failed. Illegal index."); Node cur = dummyHead.next; for (int i = 0; i < index; i++) cur = cur.next; cur.e = e; } //查找链表中是否有元素e public boolean contains(E e){ Node cur = dummyHead.next; while (cur != null){ if(cur.e.equals(e)) return true; cur = cur.next; } return false; } //从链表中删除Index(0-based)位置的元素，返回删除的元素 public E remove(int index){ if(index < 0 || index > size) throw new IllegalArgumentException("Remove failed. Illegal index."); Node prev = dummyHead; for (int i = 0; i < index; i++) prev = prev.next; Node retNode = prev.next; prev.next = retNode.next; retNode.next = null; size --; return retNode.e; } //从链表中删除第一个位置的元素 public E removeFirst(){ return remove(0); } //从链表中删除最后一个位置的元素 public E removeLast(){ return remove(size - 1); } @Override public String toString() { StringBuilder res = new StringBuilder(); for (Node cur = dummyHead.next;cur != null; cur= cur.next) res.append(cur + "->"); res.append("Null"); return res.toString(); } }
4.2.7 结果测试：
public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<>(); //添加元素 0-4 for (int i = 0; i < 5 ; i++) { linkedList.addFirst(i); System.out.println(linkedList); } //添加第二个元素添加 666 linkedList.add(2,666); System.out.println(linkedList); //删除第二个元素 666 linkedList.remove(2); System.out.println(linkedList); //删除第一个元素 linkedList.removeFirst(); System.out.println(linkedList); //删除最后一个元素 linkedList.removeLast(); System.out.println(linkedList); }
打印结果：
0->Null 1->0->Null 2->1->0->Null 3->2->1->0->Null 4->3->2->1->0->Null 4->3->666->2->1->0->Null 4->3->2->1->0->Null 3->2->1->0->Null 3->2->1->Null
