数据结构与算法系列（线性表篇）

双向链表是单链表的一种扩展，单链表中每一个节点只保存一个指针域，该指针域唯一的指向当前节点的直接后继，而双向链表在单链表节点类型的基础之上，额外增加了一个前驱指针域，该指针域指向当前节点的直接前驱，正是因为有了直接前驱指针，双向链表的插入和删除算法和单链表也略有不同

在双向链表中查找一个元素同样需要遍历链表中的元素，因此时间复杂度是O(N)

在双向链表中插入一个元素，时间复杂度是O(1)，因为插入操作仅需要对指针进行常数级别的操作，调整指针指向即可

在双向链表中删除一个元素，时间复杂度是O(1)，因为双向链表的删除操作也只需要调整指针指向即可，这也是常数级别的时间复杂度

#ifndef _DOUBLYlinkEDLIST_H
#define _DOUBLYlinkEDLIST_H

// 定义双向链表元素类型
typedef int elementType;

// 声明双向链表结构类型
struct doublylinkedlist;

// 声明双向链表迭代器类型
struct doublylinkedlistIterator;

// 声明双向链表的迭代器指针类型
typedef struct doublylinkedlist *doublylinkedlistPtr;

// 声明双向链表迭代器指针类型
typedef struct doublylinkedlistIterator *doublylinkedlistIteratorPtr;

// 定义元素指针类型
typedef elementType *elementTypePtr;

// 定义双向链表元素比较函数
typedef int (*cmpFunc)(elementType, elementType);

// 从一个数组中创建双向链表
// arr是指向数组基地址的指针
// len是数组元素的个数
// mode表示采用的是头插法还是尾插法，如果mode为0，那么是头插法，否则是尾插法
doublylinkedlistPtr createWithArr(elementTypePtr arr, int len, int mode);

// 清空双向链表
void makeEmpty(doublylinkedlistPtr list);

// 判断双向链表是否为空
// 如果为空，返回true，否则返回false
int isEmpty(doublylinkedlistPtr list);

// 统计双向链表元素的个数
int length(doublylinkedlistPtr list);

// 判断指定的元素是否是双向链表的最后一个元素
// 如果是返回1，否则返回0
int isLast(elementType e, doublylinkedlistPtr list, cmpFunc cmp);

// 返回指定元素在双向链表中的位置
// 如果不存在返回-1
int locate(elementType e, doublylinkedlistPtr list, cmpFunc cmp);

// 寻找指定元素e在双向链表中的直接前驱
// 如果不存在，返回0，否则返回1
// e的直接前驱使用pre指针接收
int findPrevious(elementType e, elementTypePtr pre, doublylinkedlistPtr list, cmpFunc cmp);

// 返回指定元素e在双向链表中的直接后继
// 如果不存在，那么返回0，否则返回1
// e的直接后继使用next指针接收
int findNext(elementType e, elementTypePtr next, doublylinkedlistPtr list, cmpFunc cmp);

// 返回双向链表中指定位置处的数据元素
// 如果不存在，那么返回0，否则返回1
// 元素使用指针e接收
int findByIndex(int index, elementTypePtr e, doublylinkedlistPtr list);

// 删除双向链表中第一个出现的元素
// 删除成功，返回1，否则返回0
int deleteElement(elementType e, doublylinkedlistPtr list, cmpFunc cmp);

// 删除双向链表指定位置上的元素
// 删除成功，返回1，否则返回0
// 被删除的元素使用del指针来接收，该参数可以为NULL
int deleteElementByIndex(int index, elementTypePtr del, doublylinkedlistPtr list);

// 将e插入在双向链表指定的index位置上，index从0算起
// 如果插入成功，返回1，否则返回0
int insertByIndex(int index, elementType e, doublylinkedlistPtr list);

// 将元素e追加到双向链表的最后一个位置
void addLast(elementType e, doublylinkedlistPtr list);

// 将元素追加到双向链表的最后一个位置
void addFirst(elementType e, doublylinkedlistPtr list);

// 获取一个双向链表的迭代器对象
doublylinkedlistIteratorPtr getDoublylinkedlistIterator(doublylinkedlistPtr list);

// 判断当前迭代器对象中是否还包含下一个可遍历的元素
// 如果包含，返回1，否则返回0
int iteratorHasNext(doublylinkedlistIteratorPtr iterator);

// 返回迭代器中下一个可遍历的元素
// 确保在调用该方法之前，先调用iteratorHasNext()方法
// 否则该方法的行为将不能提供正常的保证
elementType iteratorNext(doublylinkedlistIteratorPtr iterator);

// 清空迭代器对象，被清空的迭代器对象可以重新使用
void zeroIterator(doublylinkedlistIteratorPtr iterator);

// 回收迭代器空间
void freeIterator(doublylinkedlistIteratorPtr iterator);

// 回收双向链表的空间
void freeDoublylinkedlist(doublylinkedlistPtr list);

#endif

#include 
#include 
#include 

#include "doublylinkedlist.h"

// 定义双向链表节点类型
struct doublylinkedlistNode {
    // 节点数据域
    elementType elem;
    // 节点的直接前驱，如果无，则为NULL
    struct doublylinkedlistNode *pre;
    // 节点的直接后继，如果无，则为NULL
    struct doublylinkedlistNode *next;
};

// 定义双向链表节点类型的指针类型
typedef struct doublylinkedlistNode *doublylinkedlistNodePtr;

// 定义双向链表节点类型
struct doublylinkedlist {
    doublylinkedlistNodePtr head;
};

// 定义双向链表迭代器类型
struct doublylinkedlistIterator {
    // 待被迭代的双向链表
    doublylinkedlistPtr list;
    // 当前正在被访问的双向链表节点
    doublylinkedlistNodePtr cur;
};

// 错误打印函数
static void fatalOf(const char *msg) {
    fprintf(stderr, "file: %s, func: %s, line: %d, info: %sn", 
            __FILE__, __func__, __LINE__, msg);
}

// 确保参数不为NULL
// argNum是传入的检查的非NULL的参数的数目
static void ensureArgsNotNull(int argNum, ...) {
    va_list valist;
    va_start(valist, argNum);
    for (int i = 0; i < argNum; i++) {
        void *tmp = va_arg(valist, void *);
        if (!tmp) {
            fatalOf("args null exception!");
        }
    }
    va_end(valist);
}

// 创建一个双向链表节点
// e用于填充当前双向链表的数据域
static doublylinkedlistNodePtr makeNode(elementType e) {
    doublylinkedlistNodePtr node = (doublylinkedlistNodePtr) malloc(sizeof(struct doublylinkedlistNode));
    if (!node) {
        fatalOf("create node failure!");
    }
    node->pre = NULL;
    node->next = NULL;
    node->elem = e;
    return node;
}

// 头插法创建双向链表
static void headInsert(elementTypePtr arr, int len, doublylinkedlistPtr list) {
    ensureArgsNotNull(2, arr, list);

    if (len < 0) {
        fatalOf("数组长度不合法");
    }

    for (int i = 0; i < len; i++) {
        doublylinkedlistNodePtr node = makeNode(arr[i]);
        if (list->head) {
            node->pre = NULL;
            node->next = list->head;
            list->head->pre = node;
        } else {
            node->pre = NULL;
            node->next = NULL;
        }
        list->head = node;
    }
}

// 释放以head为头的双向链表空间
static void freeNodes(doublylinkedlistNodePtr head) {
    doublylinkedlistNodePtr next = NULL;
    while (head) {
        next = head->next;
        free(head);
        head = next;
    }
}

// 尾插法创建双向链表
static void tailInsert(elementTypePtr arr, int len, doublylinkedlistPtr list) {
    ensureArgsNotNull(2, arr, list);
    doublylinkedlistNodePtr tail = list->head;

    for (int i = 0; i < len; i++) {
        doublylinkedlistNodePtr node = makeNode(arr[i]);
        if (!tail) {
            list->head = node;
            tail = node;
        } else {
            node->pre = tail;
            node->next = NULL;
            tail->next = node;
            tail = node;
        }
    }
}

// 从一个数组中创建双向链表
// arr是指向数组基地址的指针
// len是数组元素的个数
// mode表示采用的是头插法还是尾插法，如果mode为0，那么是头插法，否则是尾插法
doublylinkedlistPtr createWithArr(elementTypePtr arr, int len, int mode) {
    doublylinkedlistPtr list = (doublylinkedlistPtr) malloc(sizeof(struct doublylinkedlist));
    if (!list) {
        fatalOf("创建双向链表失败");
    }
    list->head = NULL;

    switch (mode) {
    case 0:
        headInsert(arr, len, list);
        break;
    
    default:
        tailInsert(arr, len, list);
        break;
    }
    return list;
}

// 清空双向链表
void makeEmpty(doublylinkedlistPtr list) {
    ensureArgsNotNull(1, list);

    freeNodes(list->head);
    list->head = NULL;
}

// 判断双向链表是否为空
// 如果为空，返回true，否则返回false
int isEmpty(doublylinkedlistPtr list) {
    ensureArgsNotNull(1, list);
    return NULL == list->head;
}

// 统计双向链表元素的个数
int length(doublylinkedlistPtr list) {
    ensureArgsNotNull(1, list);

    int len = 0;
    doublylinkedlistNodePtr cur = list->head;
    while (cur) {
        len++;
        cur = cur->next;
    }
    return len;
}

// 判断指定的元素是否是双向链表的最后一个元素
// 如果是返回1，否则返回0
int isLast(elementType e, doublylinkedlistPtr list, cmpFunc cmp) {
    ensureArgsNotNull(2, list, cmp);

    doublylinkedlistNodePtr tail = list->head;
    while (tail && tail->next) {
        tail = tail->next;
    }
    if (!tail) {
        return 0;
    }
    return !cmp(e, tail->elem);
}

// 返回指定元素在双向链表中的位置
// 如果不存在返回-1
int locate(elementType e, doublylinkedlistPtr list, cmpFunc cmp) {
    ensureArgsNotNull(2, list, cmp);

    doublylinkedlistNodePtr cur = list->head;
    int index = 0;
    while (cur && cmp(e, cur->elem) != 0) {
        cur = cur->next;
        index++;
    }
    if (!cur) {
        return 0;
    }
    return index;
}

// 寻找指定元素e在双向链表中的直接前驱
// 如果不存在，返回0，否则返回1
// e的直接前驱使用pre指针接收
int findPrevious(elementType e, elementTypePtr pre, doublylinkedlistPtr list, cmpFunc cmp) {
    ensureArgsNotNull(2, list, cmp);

    doublylinkedlistNodePtr cur = list->head;
    while (cur && cmp(e, cur->elem) != 0) {
        cur = cur->next;
    }
    if (!cur) {
        return 0;
    }
    if (!cur->pre) {
        return 0;
    }
    *pre = cur->pre->elem;
    return 1;
}

// 返回指定元素e在双向链表中的直接后继
// 如果不存在，那么返回0，否则返回1
// e的直接后继使用next指针接收
int findNext(elementType e, elementTypePtr next, doublylinkedlistPtr list, cmpFunc cmp) {
    ensureArgsNotNull(2, list, cmp);

    doublylinkedlistNodePtr cur = list->head;
    while (cur && cmp(e, cur->elem) != 0) {
        cur = cur->next;
    }
    if (!cur) {
        return 0;
    }
    if (!cur->next) {
        return 0;
    }
    if (next) {
        *next = cur->next->elem;
    }
    return 1;
}

// 返回双向链表中指定位置处的数据元素
// 如果不存在，那么返回0，否则返回1
// 元素使用指针e接收
int findByIndex(int index, elementTypePtr e, doublylinkedlistPtr list) {
    ensureArgsNotNull(1, list);

    doublylinkedlistNodePtr cur = list->head;
    int i = 0;
    while (i < index && cur) {
        cur = cur->next;
        i++;
    }
    if (i > index || !cur) {
        return 0;
    }
    if (e) {
        *e = cur->elem;
    }
    return 1;
}

// 删除双向链表中第一个出现的元素
// 删除成功，返回1，否则返回0
int deleteElement(elementType e, doublylinkedlistPtr list, cmpFunc cmp) {
    ensureArgsNotNull(2, list, cmp);

    doublylinkedlistNodePtr cur = list->head;

    while (cur && cmp(e, cur->elem) != 0) {
        cur = cur->next;
    }
    if (!cur) {
        return 0;
    }
    if (cur->pre && cur->next) {
        cur->pre->next = cur->next;
        cur->next->pre = cur->pre;
    } else if (cur->pre) {
        cur->pre->next = NULL;
    } else if (cur->next) {
        list->head = cur->next;
        cur->pre = NULL;
    } else {
        list->head = NULL;
    }
    free(cur);
    return 1;
}

// 删除双向链表指定位置上的元素
// 删除成功，返回1，否则返回0
// 被删除的元素使用del指针来接收，该参数可以为NULL
int deleteElementByIndex(int index, elementTypePtr del, doublylinkedlistPtr list) {
    ensureArgsNotNull(1, list);

    int i = 0;
    doublylinkedlistNodePtr cur = list->head;
    while (i < index && cur) {
        i++;
        cur = cur->next;
    }
    if (i > index || !cur) {
        return 0;
    }

    if (cur->pre && cur->next) {
        cur->pre->next = cur->next;
        cur->next->pre = cur->pre;
    } else if (cur->pre) {
        cur->pre->next = NULL;
    } else if (cur->next) {
        list->head = cur->next;
        list->head->pre = NULL;
    } else {
        list->head = NULL;
    }
    *del = cur->elem;
    free(cur);
    return 1;
}

// 将e插入在双向链表指定的index位置上，index从0算起
// 如果插入成功，返回1，否则返回0
int insertByIndex(int index, elementType e, doublylinkedlistPtr list) {
    ensureArgsNotNull(1, list);

    doublylinkedlistNodePtr newNode = makeNode(e);
    
    newNode->next = list->head;
    doublylinkedlistNodePtr pre = newNode;

    int i = -1;
    while (i < index - 1 && pre) {
        pre = pre->next;
        i++;
    }
    if (i > index - 1 || !pre) {
        return 0;
    }
    if (pre == newNode) {
        list->head->pre = newNode;
        list->head = newNode;
    } else if (pre->next) {
        newNode->next = pre->next;
        pre->next->pre = newNode;
        newNode->pre = pre;
        pre->next = newNode;
    } else {
        newNode->next = NULL;
        newNode->pre = pre;
        pre->next = newNode;
    }
    return 1;
}

// 将元素e追加到双向链表的最后一个位置
void addFirst(elementType e, doublylinkedlistPtr list) {
    ensureArgsNotNull(1, list);

    doublylinkedlistNodePtr newNode = makeNode(e);
    
    if (!list->head) {
        list->head = newNode;
        newNode->pre = NULL;
        newNode->next = NULL;
    } else {
        newNode->next = list->head;
        list->head->pre = newNode;
        list->head = newNode;
    }
}

// 将元素追加到双向链表的最后一个位置
void addLast(elementType e, doublylinkedlistPtr list) {
    ensureArgsNotNull(1, list);

    doublylinkedlistNodePtr newNode = makeNode(e);
    
    doublylinkedlistNodePtr tail = list->head;
    while (tail && tail->next) {
        tail = tail->next;
    }

    if (!tail) {
        list->head = newNode;
        newNode->pre = NULL;
        newNode->next = NULL;
    } else {
        newNode->next = tail->next;
        newNode->pre = tail;
        tail->next = newNode;
    }
}

// 获取一个双向链表的迭代器对象
doublylinkedlistIteratorPtr getDoublylinkedlistIterator(doublylinkedlistPtr list) {
    ensureArgsNotNull(1, list);

    doublylinkedlistIteratorPtr iterator = (doublylinkedlistIteratorPtr) malloc(sizeof(struct doublylinkedlistIterator));
    if (!iterator) {
        fatalOf("创建双向链表迭代器失败");
    }
    iterator->list = list;
    iterator->cur = list->head;
    return iterator;
}

// 判断当前迭代器对象中是否还包含下一个可遍历的元素
// 如果包含，返回1，否则返回0
int iteratorHasNext(doublylinkedlistIteratorPtr iterator) {
    return iterator->cur != NULL;
}

// 返回迭代器中下一个可遍历的元素
// 确保在调用该方法之前，先调用iteratorHasNext()方法
// 否则该方法的行为将不能提供正常的保证
elementType iteratorNext(doublylinkedlistIteratorPtr iterator) {
    ensureArgsNotNull(1, iterator);
    elementType e = iterator->cur->elem;
    iterator->cur = iterator->cur->next;
    return e;
}

// 清空迭代器对象，被清空的迭代器对象可以重新使用
void zeroIterator(doublylinkedlistIteratorPtr iterator) {
    ensureArgsNotNull(1, iterator, iterator->list);
    iterator->cur = iterator->list->head;
}

// 回收迭代器空间
void freeIterator(doublylinkedlistIteratorPtr iterator) {
    ensureArgsNotNull(1, iterator);
    free(iterator);
}

// 回收双向链表的空间
void freeDoublylinkedlist(doublylinkedlistPtr list) {
    ensureArgsNotNull(1, list);
    if (list->head) {
        freeNodes(list->head);
    }
    free(list);
}

cfiles=main.c doublylinkedlist.c

target=doublylinkedlist_test.exe

obj=main.o doublylinkedlist.o

cc=gcc -std=c99

$(target):$(obj)
	$(cc) $(obj) -o $(target)

$(obj):$(cfiles)
	$(cc) -c $(cfiles)

.PHONY:clean
clean:
	del $(target) $(obj)

#include 

#include "doublylinkedlist.h"

static void printList(doublylinkedlistIteratorPtr iterator) {
    while (iteratorHasNext(iterator)) {
        printf("%dn", iteratorNext(iterator));
    }
}

static int cmp(elementType e1, elementType e2) {
    if (e1 < e2) {
        return -1;
    } else if (e1 > e2) {
        return 1;
    } else {
        return 0;
    }
}

int main(void) {
    elementType elems[] = {1, 2, 3, 4, 5, 6};
    doublylinkedlistPtr list = createWithArr(elems, 6, 0);
    doublylinkedlistIteratorPtr iterator = getDoublylinkedlistIterator(list);
    printList(iterator);

    // makeEmpty(list);
    printf("isEmpty %dn", isEmpty(list));
    
    printf("length: %dn", length(list));

    elementType e = 2;
    int pos = locate(e, list, cmp);
    printf("%d pos is %dn", e, pos);

    elementType pre = 1000;
    e = 5;
    if (findPrevious(e, &pre, list, cmp)) {
        printf("%d pre is %dn", e, pre);
    } else {
        printf("%d not pren", e);
    }

    elementType next = 1000;
    e = 5;
    if (findNext(e, &next, list, cmp)) {
        printf("%d next is %dn", e, next);
    } else {
        printf("%d not nextn", e);
    }

    int index = 1;
    if (findByIndex(index, &e, list)) {
        printf("pos %d elem is %dn", index, e);
    } else {
        printf("pos %d not has elemn", index);
    }

    e = 3;
    if (deleteElement(e, list, cmp)) {
        printf("delete %d successn", e);
    } else {
        printf("delete %d failuren", e);
    }

    zeroIterator(iterator);
    printList(iterator);

    index = 0;
    e = 1000;
    if (deleteElementByIndex(index, &e, list)) {
        printf("delete pos %d elem is %dn", index, e);
        zeroIterator(iterator);
        printList(iterator);
    } else {
        printf("delete pos %d failuren");
    }

    index = length(list);
    printf("index: %dn", index);
    e = 999;
    if (insertByIndex(0, e, list)) {
        zeroIterator(iterator);
        printList(iterator);
    } else {
        printf("insert failure");
    }

    addFirst(4444, list);
    addLast(4444, list);
    
    zeroIterator(iterator);
    printList(iterator);

    freeIterator(iterator);
    freeDoublylinkedlist(list);
    return 0;
}