前言：线性表的链式描述，是最基本的数据结构，在物理空间上不必连续存储。使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是同时链表由于增加了结点的指针域，空间开销比较大。
因为链表失去了数组随机读取的优点，故查询速度要慢点。
因为数组的插入删除需要移动大量的元素，而链表只需要改变“链”的关系即可而查询比数组慢，所以其插入、删除操作比数组快。
一、链表的定义
链表（Linked list）：是线性表的链式描述，在物理存储单元上非连续、非顺序的存储，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点(链表中每一个元素称为结点）组成，结点(node)可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
上图是单链表（每一个节点只有一个链）存储原理图，head变量是头节点，每一个节点都链向下一个节点，最后一个节点的链域值为null。
节点访问：每个节点都必须从head结点开始，沿着一系列指针才能访问到，不能随机访问。
二、头结点和头指针
-
头结点：head,在单链表的第一个结点之前附设一个结点，它没有直接前驱，称之为头结点。
-
头指针：通常使用“头指针”来标识一个链表，如单链表L，头指针为NULL的时表示一个空链表。
头结点的数据域可以不存储任何信息（有时候也会存放链表的长度等信息），他的指针区域存放的是链表中第一个数据元素的结点（就是传说中的首元结点）存放的地址。
头结点的作用：
注意：无论是否有头结点，头指针始终指向链表的第一个结点。如果有头结点，头指针就指向头结点。
三、链表的Java实现
①头插法建表：
该方法从一个空表开始，读取数组a中的字符，生成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止。
链表Java实现
②手写一遍
链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，所谓的链表就好像火车车厢一样，从火车头开始，每一节车厢之后都连着后一节车厢。
Java语言中没有struct,我们可以定义一个Node类表示结点。
class Node
{//为了方便，两个变量都用public，而不用private,这样就不能用写get、set方法访问数据成员public int data;// 数据域public Node next;// 指针域public Node(int data){this.data = data;}
}利用Node类构建Chain类
public class Chain
{//数据成员public Node head; //头结点，其指针指向链表的第一个元素节点public int listSize; //链表长度public Chain(){head = new Node(listSize);//初始化链表时创建一个头结点}//检查插入或删除的索引是否合法public boolean checkIndex(int index){if(index<1||index>(listSize+1))return false;return true;｝//方法成员public void addNode(Node new Node);public boolean insertNodeByIndex(int index,Node node);public void deleteNode(int index);public int length();public void print();
}a、添加结点：addNode(Node newNode)
直接在链表最后插入新增结点，将原本最后个结点的指针指向新节点。
public void addNode(Node newNode)
{//如果头结点的指针为空，说明是空链表，直接把新节点赋予给头结点的指针head.nextif(head.next==null){head.next = newNode;return;}Node temp = head; //将头指针赋予给移动指针temp//链表中有节点，遍历单链表，直至到最后一个节点while(temp.next!=null){temp = temp.next;//temp往后移动一个节点 }temp.next = newNode;//temp为最后个节点或者是头结点，将其next指向新节点listSize++;//链表元素个数累加
}b、插入结点：insertNodeByIndex(int index,Node newNode)
为了在链表中索引为indexc处插上一个新元素，需要先找到索引为index-1的前驱节点，然后在该节点后插入新节点。此时，只要让新节点指向原来index处的节点，然后前驱节点指向新节点即可。
public boolean insertNodeByIndex(int index,Node newNode) {if(checkIndex(index)==false)return false;int pos = 1;//记录位置，即我们遍历到哪个节点了，首元节点从1开始Node temp = head;while(temp.next!=null){if(pos == index) //判断是否到达指定位置{//temp是当前位置的前驱节点newNode.next = temp.next;//让新节点指向原本处于该位置的节点temp.next = newNode;//让当前位置的前驱节点指向插入的新节点break;//结束整个循环体}pos++;temp = temp.next;//继续向下移动}listSize++;return true;
}c、删除结点：deleteNode（int index）
和插入过程相似，找到要删除位置的前驱节点，然后让前驱节点指向删除位置的下一个节点即可。最后可以让删除位置为null，方便系统gc。
public void deleteNode(int index)
{if(checkIndex(index)){System.out.println("指定位置不合理");return;}int pos = 1;//记录位置，即我们遍历到哪个节点了，首元节点从1开始Node temp = head;while(temp.next!=null){if(pos == index) //判断是否到达指定位置{//temp是当前位置的前驱节点//删除操作,让前驱节点指向要删除结点的下一个节点即可，这样该节点就不在链表中了。temp.next = temp.next.next;break;//结束整个循环体}pos++;temp = temp.next;//继续向下移动}listSize--;}d、访问索引为index的元素数据：get(int index)
public int get(int index)
{checkIndex(index);Node cur = head.next;if(cur==null){System.out.println("链表为空");}else{ //移向所需要的节点for(int i=0;i<index;i++){cur = cur.next;}}return cur.data;
}e、计算链表长度：length()
public int length()
{return listSize;
}f、遍历链表，打印出所有节点数据：print（）
public void print()
{Node cur = head.next;while(cur!=null){System.out.println(cur.data+",");cur = cur.next;//向下移动}
}四、循环链表和双向链表
- 循环链表
如果把单链表的最后一个节点的指针指向链表头部，而不是指向NULL，那么就构成了一个单向循环链表。整个链表形成一个 环。
- 双向链表
对于大多数应用，采用单链表和循环链表就够了。然而对于某些应用，如果每个元素节点既有一个指向后继的指针next，又有一个指向前驱的指针previous，就会更方便。
DoubleChain:有两个数据成员firstNode和lastNode分别指向最左边的节点和最右边的节点。当双向链表为空时，firstNode=lastNode=null。
优点：如果在双向链表中查找索引为index的元素，那么当index<listSize/2时，就从左向右查找， 否则就从优向左查找。