使用结构和指针

使用结构和指针

         链表linked list就是一些包含数据的独立数据结构(通称为节点)的集合。

clip_image002

         单链表是一种使用指针来存储值的数据结构。链表中的每个节点包含一个字段,用于指向链表的下一个节点。另外有一个独立的根指针指向链表的第一个节点。由于节点在创建时是采用动态分配内存的方式,所以他们可能分散于内存之中。但是,遍历链表时根据指针进行的,所以节点的物理排列无关紧要。单链表只能以一个方向进行遍历。

         单链表添加新节点的两个步骤:

l  新节点的link字段必须设置为指向它的目标后续节点;

l  前一个节点的link字段必须设置为指向这个新节点;

l  对于根节点,可以通过保存一个指向必须进行修改的link字段的指针,而不是保存一个指向前一个节点的指针,来消除对起始位置的影响。

clip_image004

         双链表的每个节点包含两个link字段,其中fwd为指向链表的下一个节点,bwd为指向链表的上一个节点。所以,为了把一个新节点插入到双链表中,我们必须修改4个指针。新节点的前向和后向link字段必须被设置,前一个节点的后向link和后一个节点的前向link也需要进行修改,使它们指向这个新节点。