Java数据结构与算法学习之双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。本文将为大家详细介绍双向链表的特点与使用，需要的可以参考一下

目录
双向链表的储存结构示意图
双向链表的初始化结构
1.双向链表的结点
2.双向链表的头结点
3.总代码
双向链表中的指定文件插入元素
1.插入的为第一个位置
2.其他位置插入
总代码
双向链表的删除
1.删除第一个元素
2.删除其他位置元素
总代码

双向链表的储存结构示意图

双向链表的初始化结构

1.双向链表的结点

代码实现

//双向链表的结点，包含一个数据域，两个指针域
typedef struct DoublyNode {
    ElementType date;  //数据域
    struct DoublyNode* prev;   //指向前缀结点
    struct DoublyNode* next;   //指向后缀结点
}DoublyNode;

2.双向链表的头结点

//双向链表
typedef struct DoublyLinkList {
    int length;
    DoublyNode* next;
};

3.总代码

//双向链表的结点，包含一个数据域，两个指针域
typedef struct DoublyNode {
    ElementType date;  //数据域
    struct DoublyNode* prev;   //指向前缀结点
    struct DoublyNode* next;   //指向后缀结点
}DoublyNode;
  
//双向链表
typedef struct DoublyLinkList {
    int length;
    DoublyNode* next;
};

双向链表中的指定文件插入元素 

1.插入的为第一个位置

代码实现

2.其他位置插入

代码实现

总代码

void InsertDoublyLinkList(DoublyLinkList* dlist, int pos, ElementType element) {
    //创建空节点
    DoublyNode* node = (DoublyLinkList*)malloc(sizeof(DoublyLinkList));
    node->date = element;
    node->prev = NULL;
    node->next = NULL;
    //在第一个位置插入结点
    if (pos == 1) {
        node->next = dlist->next;
        dlist->next = node;
        node->next->prev = node;
        dlist->length++;
        return;
    }
    DoublyLinkList* currNode = dlist->next;
    for (int i = 1; currNode && i < pos - 1; i++) {
        currNode = currNode->next;
    }
    if (currNode) {
        node->prev = currNode;
        if (currNode->next) {
            //如果前置结点非空->因为空就表示没有后继结点了
            //将插入位置的前置结点改为指向新结点
            currNode->next->prev = node;
        }
        node->next = currNode->next;
        currNode->next = node;
        dlist->length++;
    }
}

双向链表的删除

1.删除第一个元素

代码实现

2.删除其他位置元素

代码实现

总代码

void DeleteDoublyLinkList(DoublyLinkList* dlist, int pos) {
    if (pos == 1) {
        DoublyLinkList* node = dlist->next;
        if (node) {
            dlist->next;
            if (node->next) {
                //如果哟有第二个结点，那么设置第二个结点的前置结点为NULL
                node->next->prev = NULL;
            }
            free(node);
            dlist->length--;
        }
        return;
    }
  
    DoublyLinkList* node = dlist->next;
    for (int i = 1; i < pos; i++) {
        node = node->next;
    }
    if (node) {
        if (node->next) {
            node->next->prev = node->prve;
        }
        node->prev->next = node->next;
        free(node);
        dlist->length--;
    }
    return;
}

　　到此这篇关于Java数据结构与算法学习之双向链表的文章就介绍到这了