一、引言

思考：如果我们需要用程序来表示一个多项式,如

y = 3x^4+2x^2+1

我们可以使用哪些东西呢？

数组存储

我们可以用一个数组a[i]来存储这个多项式

我们可以看到这里我们用i来表示幂次，用a[i]来表示方程的系数。

但是这里有一个问题，如果我们要表示的式子是

y = 5x^2+x^9

我们需要一个容量为 9 的数组来存储这个多项式，我们仅仅用到了其中的两位。这时候我们就可以使用链表。

二、单链表、循环链表、双向链表

链表

链表是非常常见的一种数据结构，我们一般通过结构体来实现链表。

type struct Linked{
	int Val;
	*Linked Next;
}

可以看到链表中每个结点包含两个值，其中 Val 用于存储值，而 Next 用于存储下一个结点的地址。

1. 更快的插入和删除操作

在进行插入和删除操作时，只需要修改结点的 Next 值，不需要搬移数据。因此插入和删除操作的时间复杂度都是 O(1)

2. 查找需要遍历链表

链表不像数组存储地址连续，因此我们无法通过下表来访问值，随机访问时间复杂度 O(n)

循环链表

我们上面所描述的，就是单链表。
而循环链表无非就是让尾结点的 Next 指向头结点，这样链表就可以循环，不会出现 Next==null 的情况了。

双向链表

双向链表顾名思义就是每个链表结点上除了有和单链表一样的 Val 和 Next 之外，还多出一个值 Prev 。
Prev 和 Next 一样也是指针，Prev用于存储前一个结点的位置。这样在进行操作是，我们可以很快找到某个结点的前驱结点，不用再次遍历一遍了。

三、链表的CRUD

1.创建一个空表

List *MakeEmpty(){
    List *PtrL;
    //为PtrL申请空间
    PtrL=(List *)malloc(sizeof(List));
    PtrL->Last=-1;
    return Ptrl;
};

2.查找

int Find(ElementType X,List *PtrL){
    int i=0;
    while(i<=PtrL->Last&&PtrL->Data[i]!=X)
        i++;
    if(i>PtrL->Last) //当到最后一个都没有找到,返回-1
        return -1; 
    else return i;   //否则返回存储位置i
}

3.插入

在第i个位置插入一个值为X的元素

void Insert(ElementType X,int i,List *PtrL){
    int j;
    //判断表有没有满
    if(PtrL->Last==MAXSIZE-1){
        printf("表满");
        return 0;
    }
    //判断插入位置是否合法
    if(i<1||i>PtrL->Last+2){
        printf("位置不合法");
        return 0;
    }
    for(j=PtrL->Last;j>=i-1;j--){
        PtrL->Data[j+1]=PtrL->Data[j];
        }
    PtrL->Data[i-1]=X;
    PtrL->Last++;
    return;
    
}

4.删除

void Delete (int i,List *PtrL){
    int j;
    //检查元素位置是否合法
    if(i<1||Ptrl->Last+1){
        printf("不存在第%d个元素",i);
        return;
    }
    //把删除掉的元素之后的元素往前移动
    for(j=1;j<=PtrL->Last;j++){
        PrtL->Data[j-1]=PtrL->Data[j];
        }
    PtrL->Last--;
    return;
}

四、链表的主要操作

1.求表长（遍历）

int Length(List *PtrL){
    List *p=PtrL;
    int j=0;
    //while循环遍历整个链表，每遍历一次j++
    while(p){
        p=p->Next;
        j++;
    }
    return j;
}

时间复杂度O(n)

2.查找

List *FindKth(int K,List *PtrL){
    List *p=PtrL;
    int i=1;
    //
    while(p!=NULL&&i<K){
        p=p->Next;
        i++;
    }
    if(i==K)return p;
    
    else return NULL;
}

3.插入

（1）先构造一个新结点

（2）找到第i-1个结点

（3）修改指针，插入结点

List *Insert(ElementType X,int i,List *PtrL){
    List *p,*s;
    //如果要插在头上
    if(i==1){
        s=(List*)malloc(sizeof(List));
        s->Data=X;
        s->Next=PtrL;
        return s;
    }
    //找i结点的位置
    p=FindKth(i-1,PtrL);
    if(p==NULL){
        printf("参数i错误");
        return NULL;
    }else{
        s=(List*)malloc(sizeof(List));
        s->Data=X;
        s->Next=p->Next;
        p->Next=s;
        return PtrL;
    }
} 

4.删除

（1）先找到链表的第i-1个结点

（2）再用指针s指向要删除的结点

（3）然后修改指针，删除s结点

（4）释放s所指结点的空间

List *Delete(int i,List *PtrL){
    List *p,*s;
    //若要删除第一个结点
    if(i==1){
        s=PtrL;
        if(PtrL!=NULL) PtrL=PtrL->Next;
        else return NULL;
        free(s);
        return PtrL;
    }
    //找i结点位置
    p=FindKth(i-1,PtrL);
    if(p==NULL){
        printf("第%d个结点不存在",i-1);
        return NULL;
    }else if(p->Next==NULL){
        printf("第%d个结点不存在",i);
        return NULL;
    }else{
        s=p->Next;
        p->Next=s->Next;
        free(s);
        return PtrL;
    }
}

五、Java 中 LinkedList 的实现

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
    //省略其他代码
}

从定义我们可以看出，LinkedList 是一个双向链表，prev 和 next 用来标记头节点和尾节点。