简介
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
数组和链表
上一篇文章写了数组的一些特性，我们这里就拿数组跟链表做为比较来学习一些链表这个数据结构吧。
数组和链表在内存上的区别就跟示意图一样，上一篇文章写了，数组的一个特点就是内存的连续性，而链表不是，链表不要求所有数据都连续存储，而是用一个“指针”将他们串在一起。
单链表
单链表是最简单的一种链表，从图中可以看出，链表第一个节点（头结点）记录着链表的起始地址，用它能遍历整个链表，尾节点指针指向一个空地址null，说明链表结束了。
和数组一样，链表也有查找删除插入等操作。上一篇中写了数组的删除插入操作是很高复杂度的操作，每次删除插入都有搬移数据，复杂度为O(n)，而链表却不用，因为链表是用“指针”来存储下一节点的地址的，所以无需数据搬移，插入操作只要将前一节点指针指向待插入数据，将待插入数据的指针指向原有节点的下一节点，就完成了插入操作，删除也一样，复杂度为O(1)。
然而链表也并非是完美的，相对于数组，因为数组内存的连续性，随意数组的随机访问就可以做到O（1）的复杂度，而链表无法根据内存地址的偏移来计算出某个节点的地址，所需想要随机访问一个链表中的数据，需要遍历整个链表来找到要访问的节点，其算法复杂度是为O（n）。
#单链表的java实现 SingleList.java
public class SingleList {
private Node head=null;
public SingleList(){
head=new Node(null);
head.next=null;
}
public int length(){
int length=0;
Node temp=head;
while (temp.next!=null){
length++;
temp=temp.next;
}
return length;
}
public void addNode(Node node){
Node temp=head;
while (temp.next!=null){
temp=temp.next;
}
temp.next=node;
}
public void addNode(Node node,int index) throws Exception {
if (index<0||index>length()+1){
throw new Exception("不合法index！");
}
int currentIndex=0;
Node temp=head;
while (temp.next != null) {
if (index== currentIndex++){
node.next=temp.next;
temp.next=node;
return;
}
temp=temp.next;
}
}
public void delNode(Node node){
Node temp=head;
while (temp.next != null) {
if (temp.data==node.data){
node.next=temp.next;
temp.next=node;
return;
}
temp=temp.next;
}
}
public void delNode(int index) throws Exception {
if (index<1||index>length()+1){
throw new Exception("不合法index!");
}
Node temp=head;
int currentIndex=0;
while (temp.next != null) {
if (index==currentIndex++){
temp.next=temp.next.next;
return;
}
temp=temp.next;
}
}
public Node getNode(int index) throws Exception {
if (index < 1 || index > length() + 1) {
throw new Exception("不合法index!");
}
Node temp=head;
int currentIndex=0;
while (temp.next!=null){
if (index == currentIndex++) {
return temp;
}
temp=temp.next;
}
return null;
}
public void show(){
Node temp=head;
while (temp.next != null) {
temp=temp.next;
System.out.println(temp.data+";");
}
}
}
class Node{
public Object data;
public Node next;
public Node(Object data){
this.data=data;
}
}
#测试 main.java
public static void main(String[] args) {
SingleList singleList=new SingleList();
singleList.addNode(new Node(1));
singleList.addNode(new Node(2));
System.out.println("singleList Length="+singleList.length());
singleList.show();
try {
singleList.addNode(new Node(0),0);
} catch (Exception e) {
e.printStackTrace();
}
System.out.println("after addNode by index singleList Length="+singleList.length());
singleList.show();
try {
singleList.delNode(2);
} catch (Exception e) {
e.printStackTrace();
}
System.out.println("after delNode by index singleList Length="+singleList.length());
singleList.show();
singleList.delNode(new Node(1));
try {
System.out.println("node 2="+singleList.getNode(2));
} catch (Exception e) {
e.printStackTrace();
}
}
循环链表
循环链表也比较简单，就是在单链表的尾节点将原本指向null 的指针变为指向头结点。然后实现代码也是跟单链表差不多，只是有几个地方需要注意一下。
#CircularList.java
public class CircularList {
private Node head=null;
public CircularList(){
head=new Node(-1);
head.next=head;
}
public int length(){
int length=0;
Node temp=head;
while (temp.next!=head){
length++;
temp=temp.next;
}
return length;
}
public void addNode(Node node){
if (head.next==head){
head.next=node;
node.next=head;
}else {
Node temp=head;
while (temp.next!=head){
temp=temp.next;
}
temp.next=node;
node.next=head;
}
}
public void addNode(Node node,int index) throws Exception {
if (index<0||index>length()+1){
throw new Exception("不合法index！");
}
int currentIndex=0;
Node temp=head;
while (temp.next != head) {
if (index== currentIndex++){
node.next=temp.next;
temp.next=node;
return;
}
temp=temp.next;
}
}
public void delNode(Node node){
Node temp=head;
while (temp.next.data != head.data) {
if (temp.next.data==node.data){
temp.next=temp.next.next;
System.out.println("del:"+node.data);
return;
}
temp=temp.next;
}
}
public void delNode(int index) throws Exception {
if (index<1||index>length()+1){
throw new Exception("不合法index!");
}
Node temp=head;
int currentIndex=0;
while (temp.next != head) {
if (index==currentIndex++){
temp.next=temp.next.next;
return;
}
temp=temp.next;
}
}
public Node getNode(int index) throws Exception {
if (index < 1 || index > length() + 1) {
throw new Exception("不合法index!");
}
Node temp=head;
int currentIndex=0;
while (temp.next!=head){
if (index == currentIndex++) {
return temp;
}
temp=temp.next;
}
return null;
}
public void show(){
Node temp=head;
while (temp.next != head) {
temp=temp.next;
System.out.println(temp.data+"->"+temp.next.data);
}
}
}
循环链表实现完了，我们接下来用它来实现一个循环链表的经典问题“约瑟夫环”，这个问题的数学描述是这样的：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
# jusephus.java
public static void main(String[] args) {
jusephus(30,5,3);
}
private static void jusephus(int n,int k,int m){
CircularList circularList=new CircularList();
for (int i = 0; i < n; i++) {
circularList.addNode(new Node(i));
}
int count=m;
Node startNode=null;
try {
startNode=circularList.getNode(k);
} catch (Exception e) {
e.printStackTrace();
}
while (circularList.length()>0){
if (--count>0){
startNode=startNode.next;
}
if (count==0){
System.out.println("out:"+startNode.data+" m="+m+" c l="+circularList.length());
circularList.delNode(startNode);
startNode=startNode.next;
count=m;
}
}
}
双向链表
双向链表顾名思义不仅有一个指向下一个节点的指针，还有一个指向前一个节点的指针。
从图中可以看出，双向链表会比单链表多一个字节的内存空间来存储前驱节点，所谓有得必有失，那么双向链表比单链表多了什么特性呢？
由于多了一个前向指针，双向链表支持O（1）时间复杂度查找前驱节点，在某些情况下双向链表的插入删除操作比单链表高效；对于单链表，前面已经写了，他的插入、删除操作的时间复杂度都是O(1)，那么还有比这更高效的？这就要先看下实际情况下删除操作所包含的情况了：
很多情况下我们删除一个节点都是只知道某个值，然后要删除这个值所在节点，那么这个时候想要找到这个节点，就需要遍历整个链表，从头遍历一次找到节点然后再执行删除操作，这时候复杂度就退化到了O（n），这种情况下无论是单链表还是双向链表都没有差别；还有一种情况是我们已经知道要删除的是一个节点，删除这个节点之前我们需要得到所要删除的节点的前向节点和后续节点，对于单链表，我们想要知道前向节点就不得不重新变量所有的节点以找到它，这个时候，双向链表的优势就体现出来了，因为它不仅存储了后续节点的指针，还存储了前向节点的指针，所以这种情况下，双向链表的删除操作无需遍历找到前向节点，此时，删除节点的时间复杂度就仅为O(1)。同理，插入操作时双向链表也比单链表会高效。
总结
链表虽然相较于数组会更方便，但是因为每个节点要多存储一个或者两个指针数据，所以在内存耗费上会比数组消耗更大，所以具体使用数组还是链表还得根据实际情况来决定。
