链表

概念解释

链表(Linked List)也是线性结构，它与数组看起来非常像，但是它们的内存分配方式、内部结构和插入删除操作方式都不一样。

链表是一系列节点组成的链，每一个节点保存了数据以及指向下一个节点的指针。链表头指针指向第一个节点，如果链表为空，则头指针为空或者为null。

链表可以用来实现文件系统、哈希表和邻接表。

下图展示了一个链表，它有3个节点：

链表分为2种：

• 单向链表

• 双向链表

链表的基本操作

• InsertAtEnd — 在链表结尾插入元素

• InsertAtHead — 在链表开头插入元素

• Delete — 删除链表的指定元素

• DeleteAtHead — 删除链表第一个元素

• Search — 在链表中查询指定元素

• isEmpty — 查询链表是否为空

常见的队列代码面试题

• 倒转1个链表
• 检查链表中是否存在循环
• 返回链表倒数第N个元素
• 移除链表中的重复元素