数据结构与算法系列2.2 线性表
什么是链表？
链表是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表的链接次序实现的一系列节点组成，节点可以在运行时动态生成，每个节点包括两个部分，一个是村粗数据元素的数据域，一个是存储指针的指针域，相比于线性表顺序结构，操作复杂。由于不必须按照顺序存储，链表在插入的时候可以达到o(1)的复杂读，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。
啥是单向链表和双向链表及循环链表？
单向链表
其特点是链表的连接方向是单向的，对链表的访问要通过顺序从头部开始，链表是使用指针进行构造的链表，又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；
因为单向链表的每个节点只包含两部分,一部分存放数据变量的data,另一部分是指向下一节点的next指针
双向链表
双向链表和单向链表的差别不是很大，只是比单向链表多了一个指向直接前驱节点的指针，这样使得，可以从双向链表的任一一个节点开始，都可以方便的访问它的前驱节点和后继节点
循环链表
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
单向链表的代码实现，这里只讲几个常用到的方法
int size（）；元素的数量
boolean isEmpty（）；是否为空
boolean contains（E element); 判断是否包含某个元素
void add（E element） ；添加元素到最后
E get（int index）；返回index对应位置的元素
E set（int index，E element）；往index位置添加元素
void add（int index，E element）；往index位置添加元素
E remove（int index）； 删除index位置对应的元素
int indexOf（E element）； 查看元素的位置
void clear（）；清除所有元素
成员变量
//头节点
private Node<E> first;
// 元素的数量
protected int size;
将节点定义为内部类
public static class Node<E>{
//元素
E element;
//指针
Node<E> next;
//构造函数
public Node(E element,Node<E> next){
this.element=element;
this.next=next;
}
}
清空所有元素 clear（）
public void clear() {
size=0;
first=null;
}
将fist设置为null即可，因为当fist与节点断开连接后，该链表就会被自动回收，不必当心内存浪费
添加元素 add（int index，E element）
public void add(int index, E element) {
//检查范围是否合法
rangeCheck(index);
//如果在索引为零的地方插入
if (index==0){
first=new Node<>(element,first);
}else{
//查找插入节点的前一个节点
Node<E> prev=node(index-1);
prev.next=new Node<>(element,prev.next);
}
size++;
}
以图演示
要在1——2之间插入一个新的节点3，则要将1的指针指向3，再将3的指针指向2
在末尾添加元素
public void add(E element) {
add(size, element);
}
直接调用上一个方法即可
获得指定节点位置的元素node（int index）
//获取index位置对应的节点对象
private Node<E> node(int index){
rangeCheck(index);
Node<E> node=first;
for (int i = 0; i < index; i++) {
node=node.next;
}
return node;
}
删除元素remove（int index）
public E remove(int index) {
//检查插入位置是否合理
rangeCheck(index);
///查找要移除元素的前一个元素
//如果为零
Node<E> node = first;
if (index==0){
first=first.next;
}else{
Node<E> prev = node(index - 1);
node=prev.next;
prev.next=node.next;
}
size--;
return node.element;
}
图解
比如我要将3这个节点移除，那么我就要将1的指针指向2，即3指针指向的的节点
获取第index位置的元素
@Override
public E get(int index) {
return node(index).element;
}
设置第index位置的元素
@Override
public E set(int index, E element) {
Node<E> node = node(index);
E old= node.element;
node.element=element;
return old;
}