开发了那么多项目，你能自己手写个健壮的链表出来吗？
【摘要】 平均起来，查找、删除和在指定节点后面插入都需要搜索链表中的一半节点，需要O(N)次比较。
上次写了篇如果让你手写个栈和队列，你还会写吗？是和一个CSDN上的朋友闲聊时候给我的启发，决定在公众号里连更一下经典数据结构和算法的文章，和大家一起巩固巩固内功。
今天来手写一个链表。虽然是用Java写的，但招式只是形式，内功还是最重要的
我们知道，数组作为数据存储结构有一定的缺陷。在无序数组中，搜索时低效的；而在有序数组中，插入效率又很低；不管在哪一种数组中删除效率都很低。况且一个数组创建后，它的大小是无法改变的。
而链表可能是继数组之后第二种使用得最广泛的通用数据结构了。这里主要来讨论并写一个单链表和双向链表。
顾名思义，单链表只能从表头到表尾的顺序，每个节点中保存了指向下一个节点的指针；双向链表则可以反向遍历，因为节点中既保存了向后节点的指针，又保存了向前节点的指针。由于链表结构相对简单，这里不再赘述，直接通过程序来查看它们常见的操作：
1. 单链表
public class LinkedList { private Link first; private int nElem; //链表中节点数量 public LinkedList() { first = null; nElem = 0; } public void insertFirst(int value) {//添加头结点 Link newLink = new Link(value); newLink.next = first; //newLink-->old first first = newLink; //first-->newLink nElem ++; } public Link deleteFirst() { //删除头结点 if(isEmpty()) { System.out.println("链表为空！"); return null; } Link temp = first; first = first.next; nElem --; return temp; } /************************************************************ ***下面是有序链表的插入*** ***这样简单排序就可以用链表来实现，复杂度为O(N) ***定义一个方法，传入一个数组， ***在方法内，遍历数组并调用insert方法就可以将数组中的数据排好序 ***********************************************************/ public void insert(int value) { Link newLink = new Link(value); Link previous = null; Link current = first; while(current != null && value > current.data) { previous = current; current = current.next; } if(previous == null) { first = newLink; } else { previous.next = newLink; } newLink.next = current; nElem ++; } public Link find(int value) { //查找特定的节点 Link current = first; while(current.data != value) { if(current.next == null) return null; else current = current.next; } return current; } public Link delete(int value) { //删除特定的节点 Link current = first; Link previous = first; while(current.data != value) { if(current.next == null) { return null; } previous = current; current = current.next; } if(current == first) { first = first.next; } else { previous.next = current.next; } nElem --; return current; } public void displayList() { if(isEmpty()){ System.out.println("链表为空！"); return; } Link current = first; while(current != null) { current.displayLink(); current = current.next; } System.out.println(" "); } public boolean isEmpty() { return (first == null); } public int size() { return nElem; }}class Link { public int data; public Link next; public Link(int data) { this.data = data; this.next = null; } public void displayLink() { System.out.print("{" + data + "} "); }}2. 双向链表
public class DoublyLinkedList { private Node first; //头节点 private Node last; //尾节点 private int size; public DoublyLinkedList() { first = null; last = null; size = 0; } public int size() { return size; } public boolean isEmpty() { return (first == null); } public void insertFirst(long value) { //插入头节点 Node newLink = new Node(value); if(isEmpty()) { last = newLink; } else{ first.previous = newLink; //newLink <-- oldFirst.previous newLink.next = first; //newLink.next --> first } first = newLink; //first --> newLink size ++; } public void insertLast(long value) {//插入尾节点 Node newLink = new Node(value); if(isEmpty()){ first = newLink; } else { last.next = newLink; //newLink <-- oldLast.next newLink.previous = last; //newLink.previous --> last } last = newLink; size ++; } public Node deleteFirst() {//删除头结点 if(first == null) { System.out.println("链表为空！"); return null; } Node temp = first; if(first.next == null) { //只有一个节点 last = null; } else { first.next.previous = null; } first = first.next; size --; return temp; } public Node deleteLast() {//删除尾节点 if(last == null) { System.out.println("链表为空"); return null; } Node temp = last; if(last.previous == null) { //只有一个节点 first = null; } else { last.previous.next = null; } last = last.previous; size --; return temp; } public boolean insertAfter(long key, long value) { //在key后面插入值为value的新节点 Node current = first; while(current.data != key) { current = current.next; if(current == null) { System.out.println("不存在值为" + value + "的节点！"); return false; } } if(current == last) { insertLast(value); } else { Node newLink = new Node(value); newLink.next = current.next; current.next.previous = newLink; newLink.previous = current; current.next = newLink; size ++; } return true; } public Node deleteNode(long key) {//删除指定位置的节点 Node current = first; while(current.data != key) { current = current.next; if(current == null) { System.out.println("不存在该节点！"); return null; } } if(current == first) { deleteFirst(); } else if(current == last){ deleteLast(); } else { current.previous.next = current.next; current.next.previous = current.previous; size --; } return current; } public void displayForward() { //从头到尾遍历链表 System.out.println("List(first --> last): "); Node current = first; while(current != null) { current.displayLink(); current = current.next; } System.out.println(" "); } public void displayBackward() { //从尾到头遍历链表 System.out.println("List(last --> first): "); Node current = last; while(current != null) { current.displayLink(); current = current.previous; } System.out.println(" "); }}class Node { public long data; public Node next; public Node previous; public Node(long value) { data = value; next = null; previous = null; } public void displayLink() { System.out.print(data + " "); }}在表头插入和删除速度很快，仅需改变一两个引用值，所以花费 O(1) 的时间。平均起来，查找、删除和在指定节点后面插入都需要搜索链表中的一半节点，需要O(N)次比较。在数组中执行这些操作也需要 O(N) 次比较，但是链表仍然要比数组快一些，因为当插入和删除节点时，链表不需要移动任何东西，增加的效率是很显著的，特别是当复制时间远远大于比较时间的时候。
当然，链表比数组优越的另一个重要方面是链表需要多少内存就可以用多少内存，并且可以扩展到所有可用内存。数组的大小在它创建的时候就固定了，所以经常由于数组太大导致效率低下，或者数组太小导致空间溢出。可变数组可以解决这个问题，但是它经常只允许以固定大小的增量扩展，这个解决方案在内存使用率上来说还是比链表要低。
作者：云享专家倪升武
来源：微信公众号
原文链接：link
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）