链表1: 静态单链表

单链表的结构

链表包含了数据域与指针域,

数据域存储数据,

指针域存储下一个结点的地址

链表的特点

链表的优势在于数据的删改, 在链表中查询第$i$个元素需要从第一个结点开始遍历链表,, 因此在数据的顺序读取中链表的优势不如数组.

链表的插入操作

设newNode为新节点, curNode为将插入的位置的结点, preNode为curNode的前驱

链表在进行插入时

1.将newNode的后继指向curNode

2.将preNode的后继指向newNode

链表的删除操作

设Node2为需要删除结点, Node1为Node2的前驱, Node3为Node2的后继

链表在进行删除时

1.将Node1的后继指向Node2后继的后继

2.将Node2后继指向NULL

3.释放Node2的内存空间

定义静态单链表的数据结构

// 静态链表创建
typedef struct LinkNode{
    int data; //链表数据域
    struct LinkNode *next; //链表指针域
}LinkNode;

测试

int main(){
    // 链表在前进到下一个元素时, 不能用p++, ++跳跃四个字节
    LinkNode node1 = {10,NULL};
    LinkNode node2 = {20,NULL};
    LinkNode node3 = {30,NULL};
    LinkNode node4 = {40,NULL};
    //在结点之间建立连接
    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;

    LinkNode *p = &node1; // 定义指针p指向当前节点
    // 遍历链表
    while(p){ //不为空时遍历链表
        // cout << (*p).data << endl;
        cout << p->data << endl;
        p = p->next;
    }
    system("pause");
    return 0;
}