温习一下c语言的双向链表

双向链表是一种常见的数据结构，链表中的每一个节点都保存了上一个和下一个元素的位置，所以表现为增删元素效率较高，查找元素效率较低，但是都能很容易的查找指定节点的前后节点。

//
//  BookNode.h
//  c_study
//
//  Created by VV on 2019/2/23.
//  Copyright © 2019年 SGQ. All rights reserved.
//

#ifndef BookNode_h
#define BookNode_h

#include <stdio.h>
#include <stdbool.h>

typedef struct BookNode_{
    char *name;
    struct BookNode_ *pre;
    struct BookNode_ *next;
} BookNode;


typedef struct BookList_ {
    BookNode *firstBook;
    BookNode *lastBook;
    int length;
} BookList;

// init a book with name
BookNode *createBookNode(char *bookName);

// print bookNode's name
void printBookName(BookNode *book);
// print bookList
void printBookListWithOrder(BookList *list, bool headToTail);
// print bookNode's name is bookList at a specified postion
void printTargetIndexBookNameInBookList(BookList *list, int position);

// insert a bookNode to head of a bookList
int insertBookToHead(BookList *list, char *bookName);
// insert a bookNode to tail of a bookList
int insertBookToTail(BookList *list, char *bookName);

// delete a bookNode from head
void popHeadBookInBookList(BookList *bookList);
// delete a bookNode from tail
void popTailBookInBookList(BookList *bookList);


#endif /* BookNode_h */

//
//  BookNode.c
//  c_study
//
//  Created by VV on 2019/2/23.
//  Copyright © 2019年 SGQ. All rights reserved.
//

#include "BookNode.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

BookNode *createBookNode(char *bookName) {
    if (!strlen(bookName)) {
        printf("bookName is empty!!\n");
        return NULL;
    }
    
    BookNode *bookNode = malloc(sizeof(BookNode));
    bookNode->name = bookName;
    bookNode->next = NULL;
    bookNode->pre  = NULL;
    return bookNode;
}

void printBookName(BookNode *book) {
    if (book != NULL) {
        printf("%s\n", book->name);
    } else {
        printf("book is NULL!!\n");
    }
}

void printTargetIndexBookNameInBookList(BookList *list, int position) {
    if (list == NULL) {
        printf("list is NULL!!\n");
        return;
    }
    
    if (list->length == 0) {
        printf("list is empty !!\n");
    }
    
    if (position < 0 || position >= list->length) {
        printf("postion should be bigger than zero and less than list's length");
    }
    
    int length = list->length;
    if (position < length / 2) {
        int index = 0;
        BookNode *node = list->firstBook;
        while (true) {
            if (index == position) {
                // found
                printBookName(node);
                break;
            } else {
                index ++;
                node = node->next;
            }
        }
    } else {
        position = list->length - 1 - position;
        int index = 0;
        BookNode *node = list->lastBook;
        
        while (true) {
            if (index == position) {
                // found
                printBookName(node);
                break;
            } else {
                index ++;
                node = node->pre;
            }
        }
    }
}

void printBookListWithOrder(BookList *list, bool headToTail) {
    if (list == NULL) {
        printf("list is NULL!!\n");
        return;
    }
    
    if (list->length == 0) {
        printf("list is empty !!\n");
    }
    
    BookNode *book = headToTail ? list->firstBook : list->lastBook;
    while (book != NULL) {
        printBookName(book);
        
        book = headToTail ? book->next : book->pre;
    }
}

int insertBookToHead(BookList *list, char *bookName) {
    if (list == NULL) {
        return -1;
    }
    
    BookNode *bookNode = createBookNode(bookName);
    if (bookNode == NULL) {
        return -1;
    }
    
    bookNode->next = list->firstBook;
    bookNode->pre  = NULL;
    
    if (list->firstBook != NULL) {
        list->firstBook->pre = bookNode;
    }
    
    list->firstBook = bookNode;
    
    if (list->length == 0) {
        list->lastBook = bookNode;
    }
    
    list->length ++;
    
    return 1;
}

int insertBookToTail(BookList *list, char *bookName) {
    if (list == NULL) {
        return -1;
    }
    
    BookNode *bookNode = createBookNode(bookName);
    if (bookNode == NULL) {
        return -1;
    }
    
    bookNode->pre  = list->lastBook;
    bookNode->next = NULL;
    
    if (list->lastBook != NULL) {
        list->lastBook->next = bookNode;
    }
    
    list->lastBook = bookNode;
    
    if (list->firstBook == NULL) {
        list->firstBook = bookNode;
    }
    
    list->length ++;
    
    return 1;
}

void popHeadBookInBookList(BookList *bookList) {
    if (bookList == NULL) {
        printf("booklist is empty!!\n");
        return;
    }
    
    if (bookList->length == 0) {
        printf("booklist is empty!!\n");
        return;
    }
    
    printf("------ [%s] has been deleted-------\n", bookList->firstBook->name);
    
    if (bookList->firstBook->next != NULL) {
        bookList->firstBook = bookList->firstBook->next;
        
        free(bookList->firstBook->pre);
        bookList->firstBook->pre = NULL;
    } else {
        free(bookList->firstBook);
        bookList->firstBook = NULL;
    }
    
    bookList->length --;
    
    if (bookList->length == 0) {
        bookList->lastBook = NULL;
    }
    
}

void popTailBookInBookList(BookList *bookList) {
    if (bookList == NULL) {
        printf("booklist is NULL!!\n");
        return;
    }
    
    if (bookList->length == 0) {
        printf("booklist is empty!!\n");
        return;
    }
    
    printf("------ [%s] has been deleted-------\n", bookList->lastBook->name);
    
    if (bookList->lastBook->pre != NULL) {
        bookList->lastBook = bookList->lastBook->pre;
        
        free(bookList->lastBook->next);
        bookList->lastBook->next = NULL;
    } else {
        free(bookList->lastBook);
        bookList->lastBook = NULL;
    }
    
    bookList->length --;
    
    if (bookList->length == 0) {
        bookList->firstBook = NULL;
    }
    
}

#include <stdio.h>
#include "BookNode.h"

int main(int argc, const char * argv[]) {
    // insert code here...
    BookList list = {NULL, NULL, 0, };
    insertBookToTail(&list, "0");
    insertBookToTail(&list, "1");
    insertBookToTail(&list, "2");
    insertBookToTail(&list, "3");
    insertBookToTail(&list, "4");
    printBookListWithOrder(&list, true);
    printf("----------");
    printTargetIndexBookNameInBookList(&list, 4);
    
//    popTailBookInBookList(&list);
//    popTailBookInBookList(&list);
//    popTailBookInBookList(&list);
//    popTailBookInBookList(&list);
//    popTailBookInBookList(&list);

    return 0;
}