数据结构之双向链表，实现双向链表的增删改查_建立一个双向链表,并且写出删除节点,尾节点追加节点

 

---

一、双向链表的定义

双向链表里有两个指针，一个指向前向节点，一个指向后续节点。

当链表为空的时候，phead->next = phead; phead->prev = phead;

1.双向链表节点的定义

//双向链表节点的定义
typedef int LTDataType;
 
typedef struct ListNode
{
    LTDataType data;
    struct ListNode * next;
    struct ListNode * prev;
}LTNode;
 

2.双向链表的初始化

链表的初始化主要是构建节点,malloc出节点，将指针初始化为空;然后初始化一个头节点

LTNode * BuyListNode(LTDataType x)
{
    struct ListNode * newnode = (LTNode *)malloc(sizeof(struct ListNode));
    if(newnode ==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;
    
    return newnode;
}
 
LTNode * ListInit()
{
    LTNode * phead = BuyListNode(1);
    phead->next = phead;
    phead->prev = phead;
}

二、双向链表的函数接口实现

1.双链表的尾插

phead->prev就是最后一个节点，改变指针的指向，代码如下：

void LTPushBack(LTNode * phead,LTDataType x)
{
    assert(phead);
    LTNode * newnode = BuyListNode(x);
    LTNode * tail = phead->prev;
    
    //插入 前面
    tail->next = newnode;
    newnode->prev = tail;
    //后面
    newnode->next = phead;
    phead->prev = newnode;
 
}

2.双向链表的尾删

删除尾节点，要保存前一个节点，tail即为phead->prev,tailPrev即为tail->prev。实现代码如下：

void LTPopBack(LTNode * phead)
{
    assert(phead);
    struct LTNode * tail = phead->prev;
    struct LTNode * tailPrev = phead->prev;
    
    tailPrev->next = phead;
    phead->prev = tailPrev;
    free(tail);
  }

3.双向链表的头插

插入前先创建节点newnode，实现代码如下：

void LTPushFront(LTNode * phead,LTDataType x)
{
    assert(phead);
    LTNode * newnode = BuyListNode(x);
    newnode->next = phead->next;
    phead->next->prev = newnode;
    
    phead->next = newnode;
    newnode->prev = phead;
}

4.双向链表的头删

删除掉本节点，要保存本节点的下一个节点，然后修改指针的指向

void LTPopFront(LTNode * phead)
{
    assert(phead);
    //如果链表为空，则不能删除
    assert(phead->next !=phead);
    
    LTNode * first = phead->next;
    LTNode * second = first->next;
    
    free(first);
    phead->next = second;
    second->prev = phead;
}

6.双向链表在pos前面插入

插入一个节点，首先先创建这个节点，pos指向当前位置，prev指向pos的前一个（prev）,修改prev的指向，prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode;

void LTInsert(LTNode * pos,LTDataType x)
{
    assert(pos); //判断pos位置的有效性
    LTNode * prev = pos->prev;
    LTNode * newnode = BuyListNode(x);
    prev->next = newnode;
    newnode->prev = prev;
    newnode->next = pos;
    pos->prev = newnode;
}

7.双向链表删除pos位置的节点

删除pos位置的节点，要保存Pos的前一个和后一个，链接起来

void LTErase(LTNode * pos)
{
    assert(pos）;
    LTNode * pre = pos->prev;
    LTNode * next = pos->next;
    pre->next = next;
    next->prev = pre;
}

8.双向链表的销毁

遍历销毁，最后销毁头节点

void LTDestroy(LTNode * phead)
{
    assert(phead);
    
    LTNode * cur = phead->next;
    while(cur !=phead)
    {
        LTNode * next = cur->next;
        
        free(cur); //释放掉找不到下一个，所以要保存下一个
        cur = next;
    }
    free(phead);
}

总结

本文主要介绍了双向链表以及链表的一些接口函数，技术有限，如有错误请指正。