计算机专业面试常见数据结构基础之链表

一、链表的概念与特点

链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组相比，链表的优点是插入和删除操作更加灵活，无需移动大量元素，但缺点是存储空间利用率较低。

链表的特点如下：

1. 顺序存储：链表中的节点按照一定的顺序排列，便于查找和遍历。

2. 动态存储：链表的节点可以根据需要动态地创建和删除，无需预先分配固定大小的空间。

3. 分散存储：链表的节点可以存储在内存中的任意位置，不受连续空间限制。

二、链表的类型

根据节点中指针的个数，链表可以分为几种类型：

1. 单链表：每个节点只有一个指向下一个节点的指针。

2. 双向链表：每个节点包含两个指针，分别指向前一个节点和后一个节点。

3. 循环链表：链表的一个节点的指针指向链表的首节点，形成一个环。

三、链表的常见操作

1. 创建链表：使用头插法或尾插法创建链表。

2. 查找元素：通过遍历链表，查找指定元素。

3. 插入元素：在链表的指定位置插入一个新节点。

4. 删除元素：删除链表中指定位置的节点。

5. 反转链表：将链表中的节点顺序颠倒。

四、单链表实现示例

是一个使用C语言实现的单链表创建、插入、删除和查找的示例：

c

#include

#include
// 定义链表节点结构体
typedef struct Node {
int data;
struct Node *next;
} Node;
// 创建节点
Node* createNode(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 创建链表
Node* createList(int arr[], int n) {
Node *head = NULL, *tail = NULL;
for (int i = 0; i < n; i++) {
Node *newNode = createNode(arr[i]);
if (head == NULL) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
}
return head;
}
// 查找元素
Node* findNode(Node *head, int data) {
Node *current = head;
while (current != NULL) {
if (current->data == data) {
return current;
}
current = current->next;
}
return NULL;
}
// 插入元素
void insertNode(Node *head, int data, int position) {
Node *newNode = createNode(data);
if (position == 0) {
newNode->next = head;
head = newNode;
} else {
Node *current = head;
for (int i = 0; i < position – 1 && current != NULL; i++) {
current = current->next;
}
if (current == NULL) {
printf("Position out of range.\n");
free(newNode);
return;
}
newNode->next = current->next;
current->next = newNode;
}
}
// 删除元素
void deleteNode(Node *head, int data) {
Node *current = head, *previous = NULL;
while (current != NULL && current->data != data) {
previous = current;
current = current->next;
}
if (current == NULL) {
printf("Element not found.\n");
return;
}
if (previous == NULL) {
head = current->next;
} else {
previous->next = current->next;
}
free(current);
}
// 打印链表
void printList(Node *head) {
Node *current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// 主函数
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
Node *head = createList(arr, n);
printList(head);
insertNode(head, 6, 2);
printList(head);
deleteNode(head, 3);
printList(head);
Node *node = findNode(head, 4);
if (node != NULL) {
printf("Element found: %d\n", node->data);
} else {
printf("Element not found.\n");
}
return 0;
}

五、

链表是计算机专业面试中常见的基础之一。熟练掌握链表的基本概念、类型、操作和实现方法，对于计算机专业的学生来说至关重要。在实际开发过程中，链表的应用十分广泛，如栈、队列、哈希表等数据结构都是基于链表实现的。希望本文对您有所帮助。