• 存在一个唯一的被称为"第一个"的数据元素；
• 存在一个唯一的被称为"最后一个"的数据元素；
• 除第一个元素外，每个元素均有唯一一个直接前驱;
• 除最后一个元素外，每个元素均有唯一一个直接后继。

顺序存储

 链式存储

例:线性表L=(bat，cat，eat，fat，hat)

其带头结点的单链表的逻辑状态和物理存储方式如图所示。

基本数据结构

依据上述内容，可以依据此来建立链表。

C版本

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

 class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
         val = x;
         next = null;
     }
 }

需要注意事项

1. 链表结构
2. 写程序是都需要先判断链表为空的情况
3. 通过使用多个指针操纵链表

一些题目

链表变形

typedef struct DuLNode{
  ElemType data;
  struct DuLNode *prior, *next;
}DuLNode, *DuLinkList;

跳跃列表（也称跳表）是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。

基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表，因此得名。所有操作都以对数随机化的时间进行。

跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，它的效率和红黑树以及 AVL 树不相上下，但跳表的原理相当简单，只要你能熟练操作链表，就能轻松实现一个 SkipList。