数据结构之链表

简介:

(本文参考《剑指offer》总结笔记,供学习使用)

    链表是一种动态数据结构,是因为在创建链表的时候,无须知道链表的长度。当插入一个结点时,我们只需要为新结点分配内存,然后调整指针的指向来确保新节点被链接到链表当中。由于没有闲置的内存,链表的空间效率比数组高。


    单向链表的结点定义为:

1
2
3
4
5
struct  ListNode
{
     int         m_nValue;
     ListNode*    m_pNext;
};

例:向链表中插入数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<stdio.h>
struct  ListNode
{
     int  m_nValue;
     ListNode* m_pNext;
};
void  createListNode(ListNode** pHead, int  n);
void  addToTail(ListNode** pHead,  int  value);
void  printList(ListNode** pHead);
void  main(){
     //建立头结点
     ListNode* pHead= new  ListNode();
 
     //创建链表,需要指定创建几个结点
     createListNode(&pHead,5); //这里需要注意的是,传递的头结点是一个指针的地址。在createListNode函数中传递了pHead,当我们向一个空链表中插入一个结点的时候,新插入的结点就是链表的头指针。由于此时会改动头指针,因此必须把pHead参数设为指向指针的指针,否则出了传递参数的函数pHead仍然是一个空指针
     
     //往链表的结尾添加一个结点
     printf ( "向链表中插入结点:10\n" );
     addToTail(&pHead,10);
 
     printf ( "输出链表为:\n" );
     printList(&pHead);
}
void  addToTail(ListNode** pHead,  int  value)
{    
     ListNode* pNew= new  ListNode();
     pNew->m_nValue=value;
     pNew->m_pNext=NULL;
     
     if (*pHead==NULL)
         *pHead=pNew;
     else
     {
         ListNode* pNode=*pHead;
         while (pNode->m_pNext!=NULL)
             pNode=pNode->m_pNext;
         pNode->m_pNext=pNew;
     }    
}
void  createListNode(ListNode** pHead, int  n){
     //这里需要注意的是,传递的头结点是一个指针的地址。在createListNode函数中传递了pHead,当我们向一个空链表中插入一个结点的时候,新插入的结点就是链表的头指针。由于此时会改动头指针,因此必须把pHead参数设为指向指针的指针,否则出了传递参数的函数pHead仍然是一个空指针
     int  x=0;
     ListNode* pNode=*pHead;
     printf ( "please input first ListNode number:" );
     scanf ( "%d" ,&pNode->m_nValue);
     pNode->m_pNext=NULL;
     for ( int  i=1;i<n;i++){
         printf ( "please input %d number:" ,i+1);
         ListNode* pNew= new  ListNode();
         scanf ( "%d" ,&x);
         pNew->m_nValue=x;
         pNew->m_pNext=pNode->m_pNext;
         pNode->m_pNext=pNew;
     }
}
void  printList(ListNode** pHead){
     ListNode* pNode=*pHead;
     while (pNode->m_pNext!=NULL){
         printf ( "%d->" ,pNode->m_nValue);
         pNode=pNode->m_pNext;
     }
     printf ( "%d\n" ,pNode->m_nValue);
}


例:往链表的结尾添加一个结点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void  AddToTail(ListNode** pHead,  int  value)
     //pHead是一个指向指针的指针。因为当我们往一个空链表中插入一个结点时,新插入的结点是链表
     //的头指针。由于此时会改动头指针,因此必须把pHead参数设为指向指针的指针,否则出了这个函数
     //pHead仍然是一个空指针。
     
     ListNode* pNew= new  ListNode();
     pNew->m_nValue=value;
     pNew->m_pNext=NULL;
     
     if (*pHead==NULL)
         *pHead=pNew;
     else
     {
         ListNode* pNode=*pHead;
         while (pNode->m_pNext!=NULL)
             pNode=pNode->m_pNext;
         pNode->m_pNext=pNew;
     }    

    注:由于链表中的内存不是一次性分配的,因此我们无法保证链表和数组一样是连续的。



例:从尾到头打印链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//使用栈结构打印链表
void  PrintListReversingly_Iteratively(ListNode* pHead)
{
     std::stack<ListNode*> nodes;
 
     ListNode* pNode = pHead;
     while (pNode != NULL)
     {
         nodes.push(pNode);
         pNode = pNode->m_pNext;
     }
 
     while (!nodes.empty())
     {
         pNode = nodes.top();
         printf ( "%d\t" , pNode->m_nValue);
         nodes.pop();
     }
}
 
 
//使用递归打印链表
void  PrintListReversingly_Recursively(ListNode* pHead)
{
     if (pHead != NULL)
     {
         if  (pHead->m_pNext != NULL)
         {
             PrintListReversingly_Recursively(pHead->m_pNext);
         }
  
         printf ( "%d\t" , pHead->m_nValue);
     }
}

注:基于递归代码简洁,但是当链表非常长的时候,就会导致函数调用层级很深,从而有可能导致函数调用栈溢出。显示用栈基于循环实现的代码鲁棒性更好。


本文转自 叫我北北 51CTO博客,原文链接:http://blog.51cto.com/qinbin/1919695


相关文章
|
4天前
|
缓存
数据结构之 - 链表数据结构详解: 从基础到实现
数据结构之 - 链表数据结构详解: 从基础到实现
26 6
|
4天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
79 64
|
16天前
|
Java
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
|
2天前
|
存储 Java
【数据结构】链表
【数据结构】链表
10 1
|
2天前
|
存储 缓存
数据结构3——双向链表
数据结构3——双向链表
21 1
|
5天前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
1月前
|
存储 Java 索引
【数据结构】链表从实现到应用,保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同,其元素在内存中非连续分布,通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念,包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表,说明了其拥有前后两个指针的特点,并展示了相关操作的代码实现。最后,对比了ArrayList与LinkedList的不同之处,包括它们底层实现、时间复杂度以及适用场景等方面。
51 10
【数据结构】链表从实现到应用,保姆级攻略
|
3天前
【数据结构】环形、相交、回文、分割、合并、反转链表
【数据结构】环形、相交、回文、分割、合并、反转链表
14 0
|
3天前
|
存储 C语言
数据结构--双链表
数据结构--双链表