链表 - 简书

线性表的顺序存储结构在查找指定位置的元素时操作较快，但是在插入和删除操作的时候需要移动大量数据的位置，操作较为耗时，造成这种结果的原因在于顺序存储是开辟一块连续的内存空间，各个数据之间紧紧相邻；那么解决顺序存储插入和删除问题就需要采取另外一种存储结构--链式存储；

线性表的链式存储结构

在顺序存储结构中数据元素只要存储数据元素信息就可以了，而链式存储结构还需要存储下一个结点的内存地址，即每个数据元素成为一个独立的结点，结点包含数据信息和地址信息两个部分；n个这样的结点就构成了链表，

单链表

因为结点中只存在一个地址指针，即该链表又称之为单链表

头结点

排在单链表的第一个结点前的结点叫头结点

头指针

链表第一个结点的存储位置即为头指针/ 头结点中存放的指针即为头指针

单链表的链式存储结构

typedef int ElemType;
typedef struct Node{
    ElemType data;
    struct Node * next;
}Node;
typedef struct Node* LinkList;

一个结点的构成包含数据域和指针区域；

单链表的初始化

LinkList linkListInit(){
Node* L ;
L = (Node*)malloc(sizeof(Node));
if (L == NULL) {
    printf("申请内存空间失败\n");
}
L ->next = NULL;
return L;
}

创建单链表之头插入方法

LinkList linkListCreateHeaderMethod(int numberOfNode){
Node* L ;
L = (Node*)malloc(sizeof(Node));
if (L==NULL) {
    return NULL;
}
L->next = NULL;
for (int i =0; i<numberOfNode; i++) {
    Node *p;
    p =(Node*) malloc(sizeof(Node));
    p -> data = i ;
    p->next = L->next;   //将结点插入到表头L-->|3|-->|2|-->|1|-->NULL
    L -> next = p;
}
return L;
}

头插入法创建单链表是在头指针和第一个结点之间完成插入操作，新节点的指针存放的是上一个作为第一个结点的地址即L->next；然后再讲L->next指向新节点p即可；

创建单链表之尾插入方法

LinkList linkListCreateTailMethod(int numberOfNode){
Node* L ;
L = (Node*)malloc(sizeof(Node));
if (L==NULL) {
    return NULL;
}
L -> next = NULL;
Node* tempL = L;
for (int i = 0; i<numberOfNode; i++) {
    Node* p ;
    p = (Node*)malloc(sizeof(Node));
    p ->data = i ;
    tempL -> next = p ;
    tempL = p ;
}
tempL ->next = NULL;
return L;
}

尾插入就是将新建立的结点放在链表的最后；

单链表的插入操作

int linkListInsert(LinkList list ,int index,int e){
    Node* pre ;
    pre = list;
    for (int i = 1; i<index; i++) {
        pre = pre ->next;
    }
    if (pre) {
        Node* newNode;
        newNode  = (Node*)malloc(sizeof(Node));
        newNode->data = e ;
        newNode->next = pre->next;
        pre->next = newNode;
        return 1;
    }
    return 0;
}

单链表的删除操作

int linkListDeleteNode(LinkList list ,int e){
    Node *p,*pre = NULL;                   //pre为前驱结点，p为查找的结点。
    p = list->next;
    while(p->data != e)              //查找值为x的元素
    {
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //删除操作，将其前驱next指向其后继。
    free(p);
    return 1;
}

单链表返回指定位置的结点数据

int GetElem(LinkList list,int index,ElemType *e){
    int i=1;
    LinkList p ;
    p = list ->next; // 默认链表名作为第一个结点的指针
    while (i<index&&p) {
        p = p ->next;
        i++;
    }
    if (!p||i>index) {
       return 0;
    }else{
        *e = p->data;
        return 1;
    }
}

链表