四、链表时间复杂度分析
| 功能 | 时间复杂度 |
| 增加 | O(n) |
| 删除 | O(n) |
| 修改 | O(n) |
| 查询 | O(n) |
对于增加和删除来说，如果是对链表头进行操作，那么就是 O(1) 级别的复杂度，对于查询来说，也是一样
五、链表应用
5.1 使用栈实现链表
5.1.1 接口类：
/** * @program: Data-Structures * @ClassName Stack * @description: * @author: lyy * @create: 2019-11-20 21:51 * @Version 1.0 **/ public interface Stack<E> { int getSize(); boolean isEmpty(); void push(E e); E pop(); E peek(); }
5.1.2 实现类：
import com.lyy.datasty.Mystack.Stack; //链表栈实现 public class LinkedListStack<E> implements Stack<E> { private LinkedList1<E> list; public LinkedListStack(){ list = new LinkedList1<>(); } @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.removeFirst(); } @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(); } }
5.1.3 运行结果：
public static void main(String[] args) { LinkedListStack<Integer> stack = new LinkedListStack<>(); for (int i = 0; i < 5; i++) { stack.push(i); System.out.println(stack); } stack.pop(); System.out.println(stack); }
5.1.4 结果打印：
Stack：top 0->Null Stack：top 1->0->Null Stack：top 2->1->0->Null Stack：top 3->2->1->0->Null Stack：top 4->3->2->1->0->Null Stack：top 3->2->1->0->Null
5.2 使用链表实现队列
5.2.1 接口类
/** * @program: Data-Structures * @ClassName Queue * @description: * @author: lyy * @create: 2019-11-21 21:54 * @Version 1.0 **/ public interface Queue<E> { int getSize(); boolean isEmpty(); void enqueue(E e); E dequeue(); E getFront(); }
5.2.2 实现类
public class LinkedListQueue<E> implements Queue<E>{ //设计私有的内部类，对于用户来说不需要知道链表底层实现， // 不需要知道node这个节点，对用户屏蔽编码实现的底层实现 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 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 = head.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(); } }
5.2.2 测试类
public static void main(String[] args) { LinkedListQueue<Integer> queue = new LinkedListQueue<>(); for (int i = 0; i < 10; i++) { queue.enqueue(i); System.out.println(queue); if(i % 3 ==2){ queue.dequeue(); System.out.println(queue); } } }
打印结果：
Queue：front 0->Null tail Queue：front 0->1->Null tail Queue：front 0->1->2->Null tail Queue：front 1->2->Null tail Queue：front 1->2->3->Null tail Queue：front 1->2->3->4->Null tail Queue：front 1->2->3->4->5->Null tail Queue：front 2->3->4->5->Null tail Queue：front 2->3->4->5->6->Null tail Queue：front 2->3->4->5->6->7->Null tail Queue：front 2->3->4->5->6->7->8->Null tail Queue：front 3->4->5->6->7->8->Null tail Queue：front 3->4->5->6->7->8->9->Null tail
