深入浅出数据结构之链表
常用的数据结构有数组、链表、栈、队列、散列表（哈希表）、堆、树、图等
熟悉数据结构能够帮助我们在平常工作中更好的使用
上篇文章深入浅出数据结构之数组已经深入浅出的解析过数组，本篇文章将围绕链表深入浅出的解析链表特点、适用场景以及设计如何实现
链表简介
链表分类
链表和数组都属于线性表，我们通常都喜欢把它们进行比较
链表可以看成一个个节点串起来组成的线性表，由于链表中的每个节点串起来，它不需要每个节点地址连续，只需要每个节点中去记录下一个节点位置
链表也有很多不同的分类，上述说的实际上是单向链表
在单向链表的基础上，如果尾节点（最后一个节点）的下一个节点是首节点（第一个节点），那么这个链表又可以称为单向循环链表
由于单向链表只能从头到尾正向遍历，如果希望能够反向遍历，则实现上可以将链表设计成双向的，也就是在每个节点中再去记录上一个节点位置，这被称作双向链表
链表特点
由于链表中的节点并不是连续的，在空间上是随机的，找到一个节点首先要找到上一个节点
因此在链表中不存在数组随机访问的特性，只能遍历寻找元素
因此链表中查询元素平均时间复杂度只能是O（n）
并且插入/删除元素时，也要先找到对应的元素才能进行操作，而插入/删除操作时也只需要改动前后节点的next、pre的指向关系就能够维护链表
链表带来的好处是，在不确定当前要操作多大量的数据时，能够不用像数组那样多余额外消耗性能的扩容/缩容操作
设计实现
在设计实现中，首先需要分析节点，如果想实现单向链表，那么节点至少需要两个变量分别储存值、下一个节点，如果实现双向链表则需要多存储上一个节点
对于节点使用的通用性，可以将节点存储的元素设置为泛型
而在链表中至少需要一个变量来记录首节点（第一个节点），如果是双向链表还可以记录尾节点（最后一个节点）
还可以在链表中记录节点数量
public class LinkedList<T> { //记录节点数量 private int size = 0; //首节点 private Node<T> first; private static class Node<T> { //泛型 通用元素 T element; //下一个节点 Node<T> next; public Node(T element, Node<T> next) { this.element = element; this.next = next; } } }
由于链表是依赖节点的，可以将定义的节点直接设计为链表的内部类
然后可以给链表提供一些可使用的方法
查询某个元素的方法
public int indexOf(T elements) { Node<T> node=first; if (elements==null){ for (int i = 0; i < size; i++) { if (node.element==null) return i; } }else { for (int i = 0; i < size; i++) { if (elements.equals(node.element)) return i; node=node.next; } } return -1; }
插入/删除方法
//最好：O(1) 最坏：O(n) 平均：O(n) public void add(int index, T element) { rangeCheckForAdd(index);//先检查index是不是错的 if (index==0){ first = new Node<T>(element,first); }else { Node<T> previousNode = getNode(index - 1); previousNode.next = new Node(element, previousNode.next); } size++; } //最好：O(1) 最坏：O(n) 平均：O(n) public T remove(int index){ rangeCheck(index); Node<T> removeNode=first; if (index==0){ first=first.next; }else { Node<T> node = getNode(index - 1); removeNode= node.next; node.next=removeNode.next; } size--; return removeNode.element; } //检查下标 private void rangeCheck(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private void rangeCheckForAdd(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
如果还不熟悉链表这种数据结构，手写一个链表是最容易上手的方式
当然也可以去查看JDK中LinkedList源码的实现
总结
本篇文章围绕数据结构中的链表，深入浅出的解析链表特点、与数组区别、链表中的分类、设计实现链表思路等
链表中的节点在空间上可以是随机的，需要用额外空间记录其他节点信息，但是不会有数组扩容/缩容时的额外性能开销
链表不支持随机访问的特性，增删改查操作的前提都是以遍历链表为基础的
链表实现思路可以是单向的，只能支持正向遍历；也可以是双向的，能够支持双向遍历；还可以是成环的，尾节点记录首节点成环
实现怎样的链表需要定义好节点，链表依赖节点，可以将节点设置为链表的内部类，还可以在链表中设置变量来记录首尾信息等等
