一、链表Linked List
随机访问:类似于数组直接【1】下标查找,是一个O(1)级别的查找。
点击查看完整内容
数组和链表的对比
二、我们创建一个自己的链表
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; int size; public LinkedList(){ head = 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; head= new Node(e,head); size++; } //在链表的index(0-based)位置添加新的元素e //在链表中不是一个常用的操作,练习用 public void add(int index,E e){ if (index<0||index>size){ System.out.println("非法传值!"); } if (index==0) addFirst(e); else { Node prev = head; for (int i=0;i<index-1;i++) prev = prev.next; // Node node = new Node(e); // node.next = prev.next; // prev.next = node; prev.next = new Node(e,prev.next); size++; } } //在链表末尾添加新的元素e public void addLast(E e){ add(size,e); }
四、为链表设立虚拟头结点
private Node dummyHead; int size; public LinkedList() { dummyHead = new Node(null, null); 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) { System.out.println("非法传值!"); } Node prev = dummyHead; for (int i = 0; i < index ; i++) prev = prev.next; // Node node = new Node(e); // node.next = prev.next; // prev.next = node; prev.next = new Node(e, prev.next); size++; }
五、链表的遍历、查询、修改
// 获得链表的第index(0-based)个位置的元素 // 在链表中不是一个常用的操作,联系用: public E get(int index){ if (index < 0 || index > size) { System.out.println("非法传值!"); } 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) { System.out.println("非法传值!"); } Node cur = dummyHead.next; for (int i= 0;i<index;i++){ cur = cur.next; } cur.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(); Node cur = dummyHead.next; while (cur!=null){ res.append(cur+"->"); cur = cur.next; } res.append("NULL"); return res.toString(); }
让我们来测试一下
public class Main { public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<>(); for (int i=0;i<5;i++){ linkedList.addFirst(i); System.out.println(linkedList); } linkedList.add(2,666); 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
六、链表的删除
// 从链表中删除index(0-based)位置的元素,返回删除的元素 // 在链表中不是一个常用的操作,练习用; public E remove(int index) { if (index < 0 || index > size) { System.out.println("非法传值!"); } 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); }
测试一下
public class Main { public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<>(); for (int i=0;i<5;i++){ linkedList.addFirst(i); System.out.println(linkedList); } linkedList.add(2,666); System.out.println(linkedList); 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
七、链表的时间复杂度
八、使用链表实现栈
package Linkedlist; import stack.ArrayStack; 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.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(); } 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); } }
package stack; public interface Stack<E> { int getSize(); boolean isEmpty(); void push(E e); E pop(); E peek(); }
控制台输出
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
本文作者为DBC,转载请注明。