博客

list 链表及list_add_tail 双向链表实现分析

  • Post author:
  • Post category:其他


前几天找实习的时候，一个面试官给我留了一个题，做一个链表demo，要求实现创建、插入、删除等操作。

链表是一种常见的数据结构，它是一种物理


存储单元


上非连续、非顺序的


存储结构


，


数据元素


的逻辑顺序是通过链表中的


指针


链接次序实现的

。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储


数据元素


的数据域，另一个是存储下一个结点地址的


指针


域。

我是用C++代码来写的。首先，定义一个linklist.h文件，该文件定义了链表的结点和链表支持的方法。如下所示：


[cpp]


view plain


copy



  1. //linklist.h：定义链表结点和方法。


  2. #include <string>


  3. using




    namespace


    std;



  5. struct


    Info

  6. {

  7. string name;

    //姓名


  8. int


    id;


    //学号

  9. };


  10. //链表定义


  11. struct


    Node

  12. {

  13. Info val;

  14. Node *next;

  15. Node(Info x):val(x),next(NULL) {}

  16. };



  18. class


    LinkList

  19. {


  20. public


    :


  21. //构造函数

  22. LinkList();


  23. //在链表头部插入结点


  24. void


    InsertHead(Info val);


  25. //插入结点


  26. void


    Insert(Info val,


    int


    pos);


  27. //删除结点


  28. void


    Remove(Info val);


  29. //得到链表长度


  30. int


    Length();


  31. //链表反序


  32. void


    Reverse();


  33. //查找结点位置


  34. int


    Find(Info val);


  35. //打印链表


  36. void


    Print();


  37. //析构函数

  38. ~LinkList();


  39. private


    :

  40. Node *head;


  41. int


    length;

  42. };

然后，定义一个linklist.cpp文件，是链表方法的实现。如下所示：


[cpp]


view plain


copy



  1. //linklist.cpp：链表方法的实现。


  2. #include “stdafx.h”


  3. #include <iostream>


  4. #include “linklist.h”


  5. using




    namespace


    std;



  7. //构造函数

  8. LinkList::LinkList()

  9. {

  10. head = NULL;

  11. length = 0;

  12. }



  14. //析构函数

  15. LinkList::~LinkList()

  16. {

  17. Node *temp;


  18. for


    (


    int


    i=0;i<length;i++)

  19. {

  20. temp=head;

  21. head=head->next;


  22. delete


    temp;

  23. }

  24. }



  26. //得到链表长度


  27. int


    LinkList::Length()

  28. {


  29. return


    length;

  30. }



  32. //在链表头部插入结点


  33. void


    LinkList::InsertHead(Info val)

  34. {

  35. Insert(val,0);

  36. }



  38. //插入结点


  39. void


    LinkList::Insert(Info val,


    int


    pos)

  40. {


  41. if


    (pos<0)

  42. {

  43. cout<<

    “pos must be greater than zero”


    <<endl;


  44. return


    ;

  45. }


  46. int


    index = 1;

  47. Node *temp = head;

  48. Node *node =

    new


    Node(val);


  49. if


    (pos == 0)

  50. {

  51. node->next = temp;

  52. head = node;

  53. length++;


  54. return


    ;

  55. }


  56. while


    (temp!=NULL && index<pos)

  57. {

  58. temp=temp->next;

  59. index++;

  60. }


  61. if


    (temp == NULL)

  62. {

  63. cout<<

    “Insert failed”


    <<endl;


  64. return


    ;

  65. }

  66. node->next = temp->next;

  67. temp->next = node;

  68. length++;

  69. }



  71. //删除结点


  72. void


    LinkList::Remove(Info val)

  73. {


  74. int


    pos = Find(val);


  75. if


    (pos == -1)

  76. {

  77. cout<<

    “Delete failed”


    <<endl;


  78. return


    ;

  79. }


  80. if


    (pos == 1)

  81. {

  82. head = head->next;

  83. length–;


  84. return


    ;

  85. }


  86. int


    index = 2;

  87. Node *temp = head;


  88. while


    (index < pos)

  89. temp = temp->next;

  90. temp->next = temp->next->next;

  91. length–;

  92. }



  94. //查找结点位置


  95. int


    LinkList::Find(Info val)

  96. {

  97. Node *temp = head;


  98. int


    index = 1;


  99. while


    (temp!=NULL)

  100. {


  101. if


    (temp->val.name == val.name && temp->val.id == val.id)


  102. return


    index;

  103. temp = temp->next;

  104. index ++;

  105. }


  106. return


    -1;


    //不存在返回-1

  107. }



  109. //链表反序


  110. void


    LinkList::Reverse()

  111. {


  112. if


    (head==NULL)


  113. return


    ;

  114. Node *curNode=head,*nextNode=head->next,*temp;


  115. while


    (nextNode!=NULL)

  116. {

  117. temp=nextNode->next;

  118. nextNode->next=curNode;

  119. curNode=nextNode;

  120. nextNode=temp;

  121. }

  122. head->next=NULL;

  123. head=curNode;

  124. }



  126. //打印链表


  127. void


    LinkList::Print()

  128. {


  129. if


    (head == NULL)

  130. {

  131. cout<<

    “LinkList is empty”


    <<endl;


  132. return


    ;

  133. }

  134. Node *temp = head;


  135. while


    (temp!=NULL)

  136. {

  137. cout<<temp->val.name<<

    “,”


    <<temp->val.id<<endl;

  138. temp=temp->next;

  139. }

  140. cout<<endl;

  141. }

最后，定义一个main.cpp，用来测试链表功能，如下所示：


[cpp]


view plain


copy



  1. // main.cpp : 测试链表功能。


  2. #include “stdafx.h”


  3. #include <iostream>


  4. #include <string>


  5. #include “linklist.h”


  6. using




    namespace


    std;



  8. int


    _tmain(


    int


    argc, _TCHAR* argv[])

  9. {

  10. LinkList head;

  11. Info val1,val2,val3,val4;

  12. val1.id =1,val1.name=

    “Kevin”


    ,val2.id=2,val2.name=


    “Cathy”


    ,val3.id=3,val3.name=


    “Lucy”


    ,val4.id=4,val4.name=


    “Gravin”


    ;



  14. //测试插入功能

  15. cout<<

    “Insert test:”


    <<endl;

  16. head.InsertHead(val1);

  17. head.Print();

  18. head.Insert(val2,1);

  19. head.Print();

  20. head.Insert(val3,4);

  21. head.Print();

  22. head.InsertHead(val3);

  23. head.Insert(val4,2);

  24. head.Print();



  26. //测试反序功能

  27. cout<<

    “reverse test:”


    <<endl;

  28. head.Reverse();

  29. cout<<

    “reversed linklist is:”


    <<endl;

  30. head.Print();



  32. //测试删除功能

  33. cout<<

    “remove test:”


    <<endl;

  34. cout<<

    “the length of linklist is:”


    <<endl;

  35. cout<<head.Length()<<endl;

  36. head.Remove(val4);

  37. head.Print();

  38. cout<<

    “the length of linklist is:”


    <<endl;

  39. cout<<head.Length()<<endl;

  40. head.Remove(val4);

  41. head.Print();


  42. return


    0;

  43. }

测试结果如下图：



转自

http://www.xuebuyuan.com/1389026.html


在看内核v4l2示例


代码


driver/media/video/vivi.c时 ，看到list_add_tail()函数，现在对其进行分析：


[cpp]


view plain



copy



  1. <span style=


    “font-size:24px;”


    >


    struct


    list_head {


  2. struct


    list_head *next, *prev;

  3. };


  5. list_add_tail(&buf->vb.queue, &vid->active);


  6. /**


  7. * list_add_tail – add a new entry


  8. * @new: new entry to be added


  9. * @head: list head to add it before


  10. *


  11. * Insert a new entry before the specified head.


  12. * This is useful for implementing queues.


  13. */


  14. static


    <span style=


    “color:#3333ff;”


    >__inline__</span>


    void


    list_add_tail(


    struct


    list_head *_new,


    struct


    list_head *head)

  15. {

  16. <span style=

    “color:#3333ff;”


    >__list_add(_new, head->prev, head);</span>

  17. }



  19. /*


  20. * Insert a new entry between two known consecutive entries.


  21. *


  22. * This is only for internal list manipulation where we know


  23. * the prev/next entries already!


  24. */


  25. static


    __inline__


    void


    __list_add(


    struct


    list_head * _new,


  26. struct


    list_head * prev,


  27. struct


    list_head * next)

  28. {

  29. <span style=

    “color:#3333ff;”


    > next->prev = _new;

  30. _new->next = next;

  31. _new->prev = prev;

  32. prev->next = _new;</span>

  33. }

  34. </span>


很多地方说：这个函数完成的功能就是添加一个新的结点在head的左边，其实不然，它是

从右向左在head->priv和head两个节点之间插入_new

。


假设刚开始建立链表，只有struct list_head *head，


那么前两句话有用：将next->prev = _new;

_new->next = next;


这就是将new节点添加到head 节点的左边，那么接 下来两句没用：   _new->prev = prev;  prev->next = _new;



如果head左边已近有了其他节点，那么调用list_add_tail（）函数后，前边两句的功能一样，都是把新的节点添加在head左边，而后两句就是把新节点添加在原来head之前节点(head->priv)右边，这样就串起来了。


那list_add就反过来，把新的节点添加在head和head之后的节点(head->next)之间；



关于list_add和list_add_tail建立栈和FIFO：



list_add和list_add_tail都是在head两边插入新的节点，所以list_add先插入的节点向右移，head->next是最后插入的节点，list_add_tail先插入的节点向左移，head->next是最先插入的节点；



遍历链表都是从head开始向下，所以用list_add建立的链表先访问的是最后插入的节点，类似于栈；list_add_tail建立的链表先访问的是最先插入的节地点，类似于FIFO。