一套理解单链表的查找、插入和删除

单链表

• 优点；不要求大片连续空间，改变容量方便
• 缺点：不可随机存取，要耗费一定空间存放指针

定义一个单链表

struct LNode {          //定义单链表节点类型
    ElemType data;      //每个节点存放一个数据元素
    struct LNode *next; //指针指向下一个节点
}LNode, *LinkList

增加一个新的节点：在内存中申请一个节点所需的空间，并用指针p指向这个节点

struct LNode *p=(struct LNode *) malloc(sizeof(struct LNode));

声明一个头指针L，指向单链表的第一个节点

typedef struct LNode *LinkList

LNode * L;  or  LinkList L;
//声明一个指向单链表第一个节点的指针

typedef关键字

在定义数据类型的时候经常会涉及到很多代码，typedef关键字可以将数据类型重命名

语法为：typedef <数据类型> <别名>

代码改进后：

typedef struct LNode LNode;

LNode *p=(LNode *) malloc(sizeof(LNode));

初始化链表

不带头节点的单链表

bool InitList(LinkList &L){
    L = Null;  //空表，暂时没有任何节点，此目的是为了防止脏数据
    return true;
}

判断单链表是否为空

bool Empty(LinkList L){
    return (L==Null);
}

带头节点的单链表

bool InitList(LinkList &L){
    L = (LNode *) malloc(sizeof(LNode));   //分配一个节点
    if (L==Null)        //内存不足分配失败
        return false;
    L->next = Null;     //头节点之后暂时还没有节点
    return true;
}

相比之下带头的节点写代码更方便，不带头的节点对于第一个数据节点和后续的数据节点的处理需要不同的代码逻辑。而且空表和非空表也需要不同的逻辑

单链表的插入和删除

插入

按位序插入（带头节点）：

ListInsert（&L,i,e）:插入操作，在表L中的第i个位置插入指定的元素e

在第i个位置插入元素e（带头结点）

bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    LNode *p;   //指针p指向当前扫描到的结点
    int j=0;    //当前p指向的是第几个节点
    p=L;        //L指向头结点，头结点是第0个结点（不存数据）
    while(p!=Null && j<i-1){    //循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==Null)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;   //插入成功
}

分析：如果i = 4 (插在表中)，首先p会指向头结点，经过while循环后p会指向a3，通过malloc会申请一个结点，s指要插入的数据e，然后将s的下一个结点指向p的下一个结点，即a4；p的下一个结点在指向s；这样就完成了数据e的插入。

时间复杂度的： T(n) = O(n)

按位序插入（不头节点）：

ListInsert（&L,i,e）:插入操作，在表L中的第i个位置插入指定的元素e

在第i个位置插入元素e（带头结点），不存在第0个结点，因此在i=1的时需要特殊处理，思路和有带头结点相似

if(i==1){
    LNode *s = (LNOde *)malloc(sizeof(LNode));
    s->data = s;
    s->next = L;   
    L = s;         //头指针指向新结点
    return true;
}

当i=1的时候需要更改头指针L，当i>1的时候和带头结点代码逻辑是一样的

结点的前插操作

前插操作：在p结点之前插入结点s

分析思路：先把需要插入的新结点s还是插入到p结点后，即s结点的下一个结点还是指向p的下一个结点，p的下一个结点还是指向s；定义一个temp数据存储p的数据，从而达到p的data和s的data数据交换，这样就达到了前插操作，及在p结点之前插入结点s；

代码实现：

bool InsertProiorNode(LNode *p, LNOde *s){
    if(p==Null || s==Null)
        retrun false;
    s->next=p->next;
    p->next=s;
    ElemType temp=p->data;
    p->data=s->data;
    s->data=temp;
    retrun true;
}

删除

按位序删除操作

ListDelete(&L,i,&e): 删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值

bool ListDelete(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    LNode *p;   //指针p指向当前扫描到的结点
    int j=0;    //当前p指向的是第几个节点
    p=L;        //L指向头结点，头结点是第0个结点（不存数据）
    while(p!=Null && j<i-1){    //循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p == Null)
        return false;
    if(p->next == Null)
        retrun false;
    LNode *q=p->next;     //命令q指向被删除结点
    e=q->data;
    p->next=q->next;
    free(q);
    return 0;
}

分析：先找到第i-1位置的结点，判断第i-1的next是否有下一个结点，将当前p的指向的结点指向NUll，即断开了p->next,即删除了成功，同时需要用free()函数释放删除结点的空间。

指定结点的删除

bool DeleteNode(LNode *p){
    if(p == Null)
        return false;
    LNode *q=p->next;     //命令q指向被删除结点
    p->data=p->next->data
    p->next=q->next;
    free(q);
    return 0;
}

分析：由于删除的指定结点不确定删除结点的后面区域，指定结点的删除不仅仅是断开结点，还需要通过和后续结点交 换数据域。

单链表的查找

• GetElem（L,i）:按位查找，获取表L中第i个位置的元素的值
• LocateElem(L,e)：按值查找，在表L中查找具有给定关键字值的元素

按位查找

分析：按位查找一般考虑的是带头结点的。所以可以把带头结点当作是0结点，首先判断i是否小于0，先定义一个j是当前指向的是第几个结点，即最开始是指向第0个结点。然后通过循环可以找到第i个结点

LNOde * GetElem(LinkList L,int i){
    if(i<0)
        return false;
    LNode *p;
    int j=0;
    p=L;
    while(P!=Null && j<i){
        p=p->next;
        j++;
    }
    return p;
}

按值查找

按值查找，找到数据==e的结点

LNOde * GetElem(LinkList L,ELemType e){
    LNode *p=L->next;
    while(P!=Null && p->data != e)
        p=p->next;
    return p;
}

求表的长度

分析：想要求一个单链表的长度，可以通过头指针p一直指向它的下一个结点，并且记录指向下一个结点的次数，当下一个结点为Null的时候结束循环，这时候累加次数即单链表的长度

int Length(LinkList L){
    int len = 0;  //统计表长
    while(p->next != Null){
        p = p->next;
        len++;
    }
    retrun len;
}

总结

通过链表的插入，删除，查找的了解，我们可以发现代码的频繁。在插入和删除中我们每次都用到了查找这个功能，所以我们考虑可以将查找这段代码进行封装，从而达到代码的复用性。