数据结构之单链表

1. 链表的特点

链表是一种非线性、非顺序的物理结构，是由若干个节点组成。
链表采用的是“见缝插针”的存储方法，不要求内存连续，靠next指针关联起来。
链表的物理存储方式为随机存储，访问方式为顺序访问。
查找节点的时间复杂度为O(n)，插入、删除节点的时间复杂度为O(1)。
链表适用于写操作多，读操作少的场景。

 1 //单向链表节点的数据结构
 2 struct SingleListNode
 3 {
 4     int   nData;//当前节点的数据
 5     Node* pNext;//指向下一个节点的指针
 6 };
 7 
 8 //双向链表节点的数据结构
 9 struct DobuleListNode
10 {
11 　　int nData;//当前节点的数据
12 　　Node* pPre;//指向上一个节点的指针
13 　　Node* pNext;//指向下一个节点的指针
14 };

2. 链表的基本操作

链表的操作方式主要分为增、删、改、查，下面以单链表为例，分别以最简单的方式介绍基本用法。

首先定义一个单链表数据结构：

 1 struct SingleListNode
 2 {
 3     int             nVal;
 4     SingleListNode* pNext;
 5     SingleListNode():pNext(NULL){}
 6     SingleListNode(int nTempValue):nVal(nTempValue),pNext(NULL){}
 7 };
 8 
 9 class SingleList
10 {
11 public:
12     SingleList():m_pHead(NULL),m_nSize(0){}
13     ~SingleList(){}
14 public:
15     SingleListNode* Find(int nIndex);
16     void            Insert(int nIndex,SingleListNode* pNode);
17     SingleListNode* Remove(int nIndex);
18     void            PrintList();
19 private:
20     SingleListNode* m_pHead;
21     int             m_nSize;
22 };

2.1 查找

链表节点的查找不能通过索引快速定位，只能从头节点开始查找。

 1 SingleListNode* SingleList::Find(int nIndex)
 2 {
 3     if(nIndex < 0 || nIndex >= m_nSize)
 4     {
 5         printf("SingleList::Find:failed! the index is out of range. index is %d 
",nIndex);
 6         return NULL;
 7     }
 8 
 9     if(NULL == m_pHead)
10     {
11         printf("SingleList::Find:failed! the head node is null. 
");
12         return NULL;
13     }
14     
15     SingleListNode* pRet = m_pHead;
16     for(int i = 0;i < nIndex;i++)
17     {
18         if(pRet)
19         {
20             pRet = pRet->pNext;
21         }
22     }
23     return pRet;
24 }

2.2 更新

首先从列表中查找待更新的节点，直接把旧数据替换为新值即可。

2.3 删除

删除分为三种情况：

尾部删除：将倒数第二个节点的next指针只为空。
头部删除：将链表头节点设为原头节点的next指针。
中间删除：将前置节点的next指针指向待删除节点的next指针。中间删除和尾部删除可以采用同一段代码实现。

 1 SingleListNode* SingleList::Remove(int nIndex)
 2 {
 3     SingleListNode* pRet = NULL;
 4     if(nIndex < 0 || nIndex >= m_nSize)
 5     {
 6         printf("SingleList::Remove:failed! the index is out of range, size is %d .
 ",m_nSize);
 7         return pRet;
 8     }
 9 
10     if(NULL == m_pHead)
11     {
12         printf("SingleList::Remove:failed! the head node is null. 
");
13         return NULL;
14     }
15 
16     if(nIndex == 0)
17     {
18         pRet = m_pHead;
19         m_pHead = m_pHead->pNext;
20     }
21     else
22     {
23         SingleListNode* pPreNode = Find(nIndex - 1);
24         if(pPreNode == NULL)
25         {
26             printf("SingleList::Remove:failed! the pPre node is null.
 ");
27             return pRet;
28         }
29 
30         pRet = pPreNode->pNext;
31         if(pRet)
32         {
33             pPreNode->pNext = pRet->pNext;
34             m_nSize--;
35         }
36     }
37     
38     return pRet;
39 }

2.4 插入

尾部插入：将尾节点的next指针指向新插入的节点。
头部插入：首先将带插入的节点的next指针头节点，然后将新插入的节点设为链表头节点（注意顺序不能反）。
中间插入：首先将新节点的next指针指向插入位置的节点，然后将原始插入位置节点的前置节点的next指针指向新节点（注意顺序不能反）。中间插入和尾部插入可以采用同一段代码实现。

 1 void SingleList::Insert(int nIndex,SingleListNode* pNode)
 2 {
 3     if(NULL == pNode)
 4     {
 5         printf("SingleList::Insert:failed! the pNode is null.
 ");
 6         return;
 7     }
 8 
 9     if(nIndex < 0 || nIndex > m_nSize)
10     {
11         printf("SingleList::Insert:failed! the index is out of range, size is %d .
 ",m_nSize);
12         return;
13     }
14 
15     if(nIndex == 0)
16     {
17         //first
18         pNode->pNext = m_pHead;
19         m_pHead = pNode;
20     }
21     else
22     {
23         SingleListNode* pPre = Find(nIndex - 1);
24         if(pPre == NULL)
25         {
26             printf("SingleList::Insert:failed! the pPre node is null.
 ");
27             return;
28         }
29 
30         pNode->pNext = pPre->pNext;
31         pPre->pNext = pNode;
32     }
33     m_nSize++;
34 }

3. 链表的应用

常见的面试题中考察链表应用的场景有：

两数相加
判断链表中是否有环
删除链表的倒数第N个节点
反转链表（单链表）
回文链表
合并两个有序链表
等等，后边会单独出一篇文章介绍面试中常见的链表算法题。