一、 什么是链表？
链表是一种存储数据集合的数据结构。有以下特性：
1， 相邻元素之间通过指针连接。
2， 最后一个元素的后继指针为NULL。
3， 程序执行中，链表长度可变。
4， 链表的空间可以按需分配
5， 没有内存空间的浪费，只是指针需要额外的内存开销。
二、 什么是数组？
也是存储数据的一种数据结构。
特点：
1， 在常数时间内访问数组之内的元素。这个过程呢就是，为了访问一个数组元素，需要计算其距离数组基地址的偏移量，用一个乘法计算偏移量，加上基地址的值，就是该元素的内存地址。
2， 数组占据的是一个连续的内存块。
3， 数组大小是固定的。
4， 数组插入一个元素操作负责，需要移动该位置后面的所有元素。
三、链表和数组比较
数组随机访问时间为常数级，链表为O(n)级。
链表插入和删除元素比数组更加快捷方便。
链表比数组占用更多的内存空间。
链表大小动态可变，数组固定大小。
四、链表具体介绍
单向链表
我们通常所说的都是单向链表，包含多个结点，每个结点都有指向下一个结点的next指针，链表最后一个结点next指针值为空，表示链表结束。
链表的基本操作：
遍历、链表中插入一个元素、链表中删除一个元素
单向链表插入分三种情况：
链表的表头插入一个结点、链表的中间插入一个结点、链表的末尾插入一个结点。
同样的删除也对应三种情况:
链表的表头删除一个结点、链表的中间删除一个结点、链表的末尾删除一个结点
下面是单向链表的具体示例：
首先是结点的数据结构，包含int类型的数据和ListNode类型的next指针，构造函数以及get/set方法。
public class ListNode {
private int data;
private ListNode next;
public ListNode(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public ListNode getNext() {
return next;
}
public void setNext(ListNode next) {
this.next = next;
}
}
接下来是针对单向链表的一些具体操作，包括循环打印结点的值，计算链表的长度、插入以及删除某个结点。
public class ListTest {
public static void main(String[] args) {
ListNode listNode = new ListNode(1);
ListNode listNode1 = new ListNode(2);
ListNode listNode2 = new ListNode(3);
ListNode listNode3 = new ListNode(4);
listNode.setNext(listNode1);
listNode1.setNext(listNode2);
listNode2.setNext(listNode3);
System.out.println(getLength(listNode));
insertNode(listNode,2,new ListNode(5));
printList(listNode);
deleteNode(listNode,2);
printList(listNode);
}
//print list node
public static void printList(ListNode headNode){
ListNode listNode = headNode;
while(listNode != null){
System.out.println(listNode.getData());
listNode = listNode.getNext();
}
}
//calculate list length
public static int getLength(ListNode headNode) {
int i = 0;
ListNode currentNode = headNode;
while (currentNode != null) {
currentNode = currentNode.getNext();
i++;
}
return i;
}
//insert list node
public static ListNode insertNode(ListNode headNode,int position,ListNode listNode){
if(headNode ==null){
return listNode;
}
if( position < 1 || position > getLength(headNode) + 1) {
System.out.println("position invalid");
}else if(position == 1){
listNode.setNext(headNode.getNext());
headNode = listNode;
}else{
//include insert in the middle or in the last of the list
int i = 1;
ListNode tempNode = headNode;
while(i < position - 1){
tempNode = tempNode.getNext();
i++;
}
listNode.setNext(tempNode.getNext());
tempNode.setNext(listNode);
}
return headNode;
}
//delete list node
public static ListNode deleteNode(ListNode headNode,int position){
if(headNode == null){
System.out.println("list is empty");
}
if( position < 1 || position > getLength(headNode) + 1) {
System.out.println("position invalid");
return headNode;
}else if(position == 1){
headNode = headNode.getNext();
}else{
int i = 1;
ListNode tempNode = headNode;
while(i < position -1){
tempNode = tempNode.getNext();
i++;
}
tempNode.setNext(tempNode.getNext().getNext());
}
return headNode;
}
}
双向链表
在一个双向链表中，一个结点既知道自己的后继结点，也知道自己的前驱结点。
双向链表的缺点：
比单向链表更加占用内存空间，因为需要多一个指针指向前驱结点。
结点的插入、删除更加费时。
双向链表插入分三种情况：
链表的表头插入一个结点、链表的中间插入一个结点、链表的末尾插入一个结点
同样的删除也对应三种情况：
链表的表头删除一个结点、链表的中间删除一个结点、链表的末尾删除一个结点
下面是双向链表的具体示例：
首先是结点的数据结构，包含int类型的数据和ListNode类型的next指针，ListNode类型的pre指针，构造函数以及get/set方法。
public class DoubleListNode {
private int data;
private DoubleListNode next;
private DoubleListNode pre;
public DoubleListNode(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public DoubleListNode getNext() {
return next;
}
public void setNext(DoubleListNode next) {
this.next = next;
}
public DoubleListNode getPre() {
return pre;
}
public void setPre(DoubleListNode pre) {
this.pre = pre;
}
}
接下来是针对双向链表的一些具体操作，包括循环打印结点的值，计算链表的长度、插入以及删除某个结点。
public class DoubleListTest {
public static void main(String[] args) {
DoubleListNode listNode = new DoubleListNode(1);
DoubleListNode listNode1 = new DoubleListNode(2);
DoubleListNode listNode2 = new DoubleListNode(3);
DoubleListNode listNode3 = new DoubleListNode(4);
listNode.setNext(listNode1);
listNode1.setPre(listNode);
listNode1.setNext(listNode2);
listNode2.setPre(listNode1);
listNode2.setNext(listNode3);
listNode3.setPre(listNode2);
System.out.println(getLength(listNode));
insertNode(listNode,3,new DoubleListNode(9));
printDoubleList(listNode);
deleteNode(listNode,3);
printDoubleList(listNode);
}
//print list node data
public static void printDoubleList(DoubleListNode headNode){
DoubleListNode listNode = headNode;
while(listNode != null){
System.out.println(listNode.getData());
listNode = listNode.getNext();
}
}
//calculate list length
public static int getLength(DoubleListNode headNode) {
int i = 0;
DoubleListNode currentNode = headNode;
while (currentNode != null) {
currentNode = currentNode.getNext();
i++;
}
return i;
}
//insert list node
public static DoubleListNode insertNode(DoubleListNode headNode, int position, DoubleListNode listNode) {
if (headNode == null) {
return listNode;
}
if (position < 1 || position > getLength(headNode) + 1) {
System.out.println("position invalid");
} else if (position == 1) {
listNode.setNext(headNode);
headNode.setPre(listNode);
return listNode;
} else {
int i = 1;
DoubleListNode tempNode = headNode;
while (i < position - 1) {
tempNode = tempNode.getNext();
i++;
}
listNode.setNext(tempNode.getNext());
// if insert in the last of the list, avoid to case nullpointer
if (tempNode.getNext() != null) {
tempNode.getNext().setPre(listNode);
}
listNode.setPre(tempNode);
tempNode.setNext(listNode);
}
return headNode;
}
//delete list node
public static DoubleListNode deleteNode(DoubleListNode headNode, int position) {
if (headNode == null) {
return headNode;
}
if (position < 1 || position > getLength(headNode) + 1) {
System.out.println("invalid position");
} else if (position == 1) {
DoubleListNode listNode = headNode.getNext();
headNode = null;
return listNode;
} else {
int i = 1;
DoubleListNode tempNode = headNode;
while (i < position - 1) {
tempNode = tempNode.getNext();
i++;
}
DoubleListNode pNode = tempNode.getNext();
// if delete in the last of the list, avoid to case nullpointer
if (pNode.getNext() != null) {
tempNode.setNext(pNode.getNext());
}
pNode.getNext().setPre(tempNode);
pNode = null;
}
return headNode;
}
}
循环链表
和单向链表、双向链表都以null结尾不同，循环链表没有结束标志。轮询算法可以用循环链表来实现。
下面举两个循环链表的基本操作，遍历和计算长度。循环链表的结点和单向链表结点数据结构一致。这里不再给出。
public class CircleLIstTest {
public static void main(String[] args) {
ListNode listNode = new ListNode(1);
ListNode listNode1 = new ListNode(2);
ListNode listNode2 = new ListNode(3);
ListNode listNode3 = new ListNode(4);
listNode.setNext(listNode1);
listNode1.setNext(listNode2);
listNode2.setNext(listNode3);
listNode3.setNext(listNode);
System.out.println(getCircleListLength(listNode));
printCircleListLength(listNode);
}
// calculate list length
public static int getCircleListLength(ListNode headNode){
ListNode listNode = headNode;
int length = 0;
while(listNode != null){
listNode = listNode.getNext();
length++;
if(listNode == headNode){
break;
}
}
return length;
}
//print list node data
public static void printCircleListLength(ListNode headNode){
ListNode listNode = headNode;
while(listNode != null){
System.out.println(listNode.getData());
listNode = listNode.getNext();
if(listNode == headNode){
break;
}
}
}
}
前面已经介绍了单向链表、双向链表、循环链表以及他们的一些基本操作。下面是给出针对链表的一些问题，其中一些巧妙地思路值得学习。
问题1：找到单向链表中的倒数第n个结点。
这个问题我们可能首先想到的就是先遍历整个链表得到链表的长度（假设为m），然后在重新遍历找到第m-n+1个就是倒数第n个结点。这里的时间复杂度是O(2m-n+1)。
那么是否有更加快捷的方法呢？答案是有的。
我们可以使用散列表，也就是哈希表。哈希表可以想象成一个java中的map。我们用结点的顺序值作为key，结点作为value。那么只需要遍历一次链表，生成哈希表。然后立马就可以根据key值m-n+1，得到这个结点。这个方法时间复杂度是O（m+1）。空间复杂度为O（m）。
除了第二个方法，是否有只扫描一次链表就解决问题的方法？
这里我们采用两个指针，开始都指向链表头结点。然后让其中一个指针先走n步，然后两个指针一起往下走，当一个指针到达末尾，另外一个正好处于倒数第n个节点处。时间复杂度为O(2m-n+1)。下面是使用两个指针时的代码。
ListNode getNNode(ListNode headNode, int n) {
ListNode listNode = headNode;
ListNode tempNode = null;
for (int i = 1; i < n; i++) {
if (listNode != null) {
listNode = listNode.getNext();
}
}
while (listNode != null) {
if (tempNode == null) {
tempNode = headNode;
}else{
tempNode = tempNode.getNext();
}
listNode = listNode.getNext();
}
if(tempNode != null){
return tempNode;
}
return null;
}
问题二：假设两个单链表在某个结点相交后，成为一个单向链表，两个链表的表头结点是已知的，相交的结点未知，相交之前各自的结点数是未知的，可能相同也可能不同。设计算法找到两个链表的合并点。
这里给出一种方法。
先分别遍历两个链表获得其长度（假设m,n且m>n），然后求出两个的差值（m-n），从较长的一个链表先走（m-n）步，然后两个链表同时遍历，直到出现两个后继指针相等的情况。则该结点就是相交结点。
public ListNode getIntersectNode(ListNode list1,ListNode list2){
int i=0,j=0,sub;
ListNode temp1 = list1;
ListNode temp2 = list2;
while(temp1 != null){
i++;
temp1 = temp1.getNext();
}
while(temp2 != null){
j++;
temp2 = temp2.getNext();
}
if(i < j){
temp1 = list2;
temp2 = list1;
sub = j - i;
}else{
temp1 = list1;
temp2 = list2;
sub = i - j;
}
for(int k=0;k<sub;k++){
temp1 = temp1.getNext();
}
while(temp1 != null && temp2 != null){
if(temp1 == temp2){
return temp1;
}
temp1 = temp1.getNext();
temp2 = temp2.getNext();
}
return null;
}
问题三：约瑟夫环，N个人想选出一个领头人，他们排成一个环，沿着环每数到第M个人，就从环中排除该人，并从下一个人重新计数，找出最后留在环中的人。
这里我们就可以用循环链表来解决这个问题，假设输入时一个有N个结点的循环链表，每个结点依次有一个编号（1-N）。代码如下：
public static ListNode getPosition(int N, int M){
ListNode p = new ListNode(1);
ListNode q;
q = p;
for(int i=2;i<=N;i++){
ListNode r = new ListNode(i);
p.setNext(r);
p = r;
}
p.setNext(q);
for(int j=N;j>1;j--){
for(int k=0;k<M - 1;k++){
p = p.getNext();
}
p.setNext(p.getNext().getNext());
}
System.out.println("the result is:" + p.getData());
return p;
}
