链表
什么是链表
链表是一种真正动静的数据结构
数据存储在节点（Node）中。每一个元素都存储着下一个元素的节点，最初一个节点指向为NULL
长处：真正的动静，不须要解决固定容量的问题
毛病：丢失了随机拜访的能力
咱们能够由此实现一个根本的链表构造：
public class LinkedList<E> { private class Node{ public E e; public Node next; 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(); } }}向链表中增加元素
头部插入元素
咱们应用一个head变量来存储第一个地位的元素。
如果咱们想增加666元素，咱们其实只须要让666的next存储head节点，而后让head指向666。
两头增加元素
如果咱们想在"1"的前面插入一个元素，应该怎么做？
咱们应用一个变量prev来存储"1"这个元素，咱们须要将要插入的数据的next指向prev的next，而后将prev的next来指向node就好了。
要害就是要找到增加的节点的前一个节点
public class LinkedList<E> { private class Node { public E e; public Node next; 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 head; private int size; public LinkedList() { head = null; size = 0; } //获取链表中元素的个数 public int getSize() { return size; } //返回链表是否为空 public boolean isEmpty() { return size == 0; } //在链表头增加新的元素 public void addFirst(E e) { head = new Node(e, head); size++; } //在链表的index地位增加新的元素e //在链表中不是一个罕用的操作，练习应用 public void add(int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException("Add failed. Illegal index."); } if (index == 0) { addFirst(e); } else { Node prev = head; for (int i = 0; i < index - 1; i++) { prev = prev.next; } prev.next = new Node(e, prev.next); size++; } } //向开端插入一个元素 public void addLast(E e) { add(size, e); }}为链表设立虚构头结点
因为在两头插入咱们都要获取前一个节点，如果咱们在最后面插入就无奈获取上一个节点，由此咱们设立一个虚构头结点。这样的话所有的节点都有了前置节点。
public class LinkedList<E> { private class Node { public E e; public Node next; 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; private int size; public LinkedList() { dummyHead = new Node(null, null); size = 0; } //获取链表中元素的个数 public int getSize() { return size; } //返回链表是否为空 public boolean isEmpty() { return size == 0; } //在链表头增加新的元素 public void addFirst(E e) { add(0,e); } //在链表的index地位增加新的元素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++; } //向开端插入一个元素 public void addLast(E e) { add(size, 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); } //批改某个地位的元素，在链表中不是一个罕用的操作，练习应用 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; } @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(); }链表元素的删除
咱们如果想删除索引为2地位的元素，咱们还是须要先找到前一个节点。
prev.next就是要删除的元素，所以咱们须要将prev的next指向要删除的节点的next节点就好。
而后将delNode置为null即可。
//删除某个地位的元素并返回，在链表中不是一个罕用的操作，练习应用 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 delNode = prev.next; prev.next = delNode.next; delNode.next = null; size --; return delNode.e; } // 从链表中删除元素e public void removeElement(E e){ Node prev = dummyHead; while(prev.next != null){ if(prev.next.e.equals(e)) { break; } prev = prev.next; } if(prev.next != null){ Node delNode = prev.next; prev.next = delNode.next; delNode.next = null; size --; } }链表的工夫复杂度剖析
增加操作
- addLast(e)
O(n) - addFirst(e)
O(1) - add(index,e)
O(n)
- addLast(e)
删除操作
- removeLast(e)
O(n) - removeFirst(e)
O(1) - remove(index,e)
O(n)
- removeLast(e)
批改操作
- set(index,e)
O(n)
- set(index,e)
查找操作
- get(index)
O(n) - contains(e)
O(n)
- get(index)
应用链表实现栈
因为咱们只操作队首的话，工夫复杂度都是O(1)，所以咱们正好能够应用链表来实现栈，这样性能会大大提高。
public class LinkedListStack<E> implements Stack<E> { private LinkedList<E> list; public LinkedListStack(){ list = new LinkedList<>(); } @Override public int getSize() { return list.getSize(); } @Override public boolean isEmpty() { return list.isEmpty(); } @Override public void push(E e) { list.addFirst(e); } @Override public E pop() { return list.remove(0); } @Override public E peek() { return list.getFirst(); } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append("Stack: top "); res.append(list); return res.toString(); }}应用链表实现队列
咱们不要再应用dummyHead，因为咱们不须要操作两头元素，然而咱们要留神链表为空的状况。
public class LinkedListQueue<E> implements Queue<E> { private class Node { public E e; public Node next; 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 head,tail; private int size; public LinkedListQueue(){ head = null; tail = null; size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void enqueue(E e) { if (tail == null){ tail = new Node(e); head = tail; }else{ tail.next = new Node(e); tail = tail.next; } size ++; } @Override public E dequeue() { if (isEmpty()){ throw new IllegalArgumentException("Cannot dequeue from an empty queue."); } Node retNode = head; head = retNode.next; retNode.next = null; if (head == null){ tail = null; } size --; return retNode.e; } @Override public E getFront() { if (isEmpty()){ throw new IllegalArgumentException("Queue is empty"); } return head.e; } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append("Queue: front "); Node cur = head; while(cur != null) { res.append(cur + "->"); cur = cur.next; } res.append("NULL tail"); return res.toString(); }}