链表采用什么存储方式

链表是一种线性数据结构，与数组不同，它的元素在内存中不是连续存储的。链表采用指针的方式将元素串联在一起。因为链表结构的特性，链表的存储方式与数组有所不同。下面从多个角度来探讨链表的存储方式。

1. 链表节点的定义

链表的核心是节点。每个节点存储两部分信息，一部分是数据本身，另一部分是指向下一个节点的指针。对于单向链表而言，节点只有一个指针，指向下一个节点；双向链表则多了一个指向前一个节点的指针。节点的存储方式可以直接使用结构体来定义，例如C语言中可以使用如下代码：

```

typedef struct ListNode {

int val;

struct ListNode *next;

} ListNode;

```

该结构体定义了一个链表节点，包括一个整型数据和一个指向下一个节点的指针。这里使用了结构体指针，因为结构体中包含指向自身的指针。

2. 链表的存储

链表的存储与数组不同，它的元素在内存中是不连续的。因为每个节点包含自身数据和指针信息，所以节点需要单独在内存中开辟空间。链表的存储空间可以通过动态内存分配来实现。在C语言中，可以使用malloc函数来动态分配内存。例如，下面的代码可以创建一个包含三个节点的链表：

```

ListNode *head = (ListNode*)malloc(sizeof(ListNode));

ListNode *node1 = (ListNode*)malloc(sizeof(ListNode));

ListNode *node2 = (ListNode*)malloc(sizeof(ListNode));

head->val = 1;

head->next = node1;

node1->val = 2;

node1->next = node2;

node2->val = 3;

node2->next = NULL;

```

该代码创建了一个三个节点的链表，每个节点包含一个整型数据和指向下一个节点的指针。第一个节点的指针指向第二个节点，第二个节点的指针指向第三个节点，第三个节点的指针为NULL，表示链表结束。

3. 链表的遍历

链表的遍历需要从头节点开始，依次沿着指针访问链表中的每个节点。在遍历过程中，可以对每个节点进行操作，例如输出节点的数据。链表的遍历方式有两种，一种是循环遍历，另一种是递归遍历。

循环遍历的代码如下：

```

ListNode *p = head;

while (p) {

printf("%d ", p->val);

p = p->next;

}

```

在循环遍历中，使用一个节点指针p来遍历链表中的每个节点。当p为NULL时，表示链表已经遍历完毕。

递归遍历的代码如下：

```

void traverse(ListNode *p) {

if (!p) return;

printf("%d ", p->val);

traverse(p->next);

}

```

在递归遍历中，使用递归函数traverse来遍历链表中的每个节点。当p为NULL时，递归结束。

4. 链表的删除和插入

链表支持插入和删除操作。插入操作可以在指定位置插入一个节点，删除操作可以删除指定位置的节点。在删除节点时，需要将该节点的前一个节点的指针指向该节点的下一个节点，以保证链表的正确性。

单向链表的插入操作代码如下：

```

void insert(ListNode *head, int val, int pos) {

ListNode *new_node = (ListNode*)malloc(sizeof(ListNode));

new_node->val = val;

ListNode *p = head;

for (int i = 0; i < pos - 1; i++) {

p = p->next;

}

new_node->next = p->next;

p->next = new_node;

}

```

该代码在链表的第pos个位置插入一个值为val的节点。先创建一个新的节点，然后找到链表中第pos个位置的节点，并将新节点的指针指向该节点的下一个节点，最后将该节点的指针指向新节点。

单向链表的删除操作代码如下：

```

void delete(ListNode *head, int pos) {

ListNode *p = head;

for (int i = 0; i < pos - 1; i++) {

p = p->next;

}

ListNode *temp = p->next;

p->next = p->next->next;

free(temp);

}

```

该代码删除链表中第pos个位置的节点。找到该节点的前一个节点，并将其指针指向该节点的下一个节点，最后释放该节点的空间。

5. 链表的优缺点

链表的存储方式是灵活的，可以根据实际需求动态分配内存，不需要预先分配。链表还支持插入和删除操作，可以在已有链表的基础上进行添加或删除元素，无需移动其他元素。这使得链表很适合于需要频繁添加或删除元素的场景。

然而，链表也有缺点。每个节点需要额外的空间存储指针信息，这增加了空间开销。链表的随机访问效率不够高，需要遍历整个链表才能找到指定位置的节点。这使得链表不适合需要频繁进行随机访问的场景。