Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Just like writing some functional interfaces of a single linked list, let's first write some interfaces of a double linked list to familiarize ourselves with its main framework:

#include<stdio.h>
#include<stdlib.h>

typedef int LDataType;

//Node of a bidirectional headed circular linked list
typedef struct ListNode{
    LDataType _data;
//Point to the starting position of the next node
    struct ListNode* _next;
//Point to the starting position of the previous node
    struct LIst* _prev;
}ListNode;

//Bidirectional headed circular linked list
typedef struct List{
    struct ListNode* _head;
}List;

struct ListNode* createListNode(LDataType val){
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->_data = val;
    node->_next = NULL;
    node->_prev = NULL;
}

void ListInit(List* lst){
//Empty linked list
    lst->_head = createListNode(0);
    lst->_head->_next = lst->_head->_prev = lst->_head;

}
//Tail insertion O(1) //Insert a data in front of the head ListInsert(lst, lst-&gt;_head, val);
void ListpushBack(List* lst, LDataType val){
    if (lst == NULL){
        return;
        struct ListNode* last = lst->_head->_prev;
        struct ListNode* newNode = createListNode(val);
        //_head ... last newNode
        last->_next = newNode;
        newNode->_prev = last;

        newNode->_next = lst->_head;
        lst->_head->_prev = newNode;
    }
}

//Tail deletion: //Delete the previous node of the head ListErase(lst, lst-&gt;_head-&gt;_prev);
void ListPopBack(List* lst){
    if (lst == NULL)
        return;
// Check if the linked list is empty
    if (lst->_head->_next == lst->_head)
        return;
    struct ListNode* last = lst->_head->_prev;
    struct ListNode* prev = last->_prev;

    free(last);

    lst->_head->_prev = prev;
    prev->_next = lst->_head;
}

void printList(List* lst){
    struct ListNode* cur = lst->_head->_next;
    while (cur != lst->_head){
        printf("%d", cur->_data);
        cur = cur->_next;
    }
    printf("n");
}

//Head insertion//ListInsert(lst,lst-&gt;_head-&gt;_next,val);
void ListPushFront(List* lst, LDataType val){
    if (lst == NULL)
        return;
    struct ListNode* next = lst->_head->_next;
    struct ListNode* newNode = createListNode(val);

    //_head, newNode, next
    lst->_head->_next = newNode;
    newNode->_prev = lst->_head;

    newNode->_next = next;
    next->_prev = newNode;
}

//Header deletion//ListErase(lst,lst-&gt;_head-&gt;_next);
void ListPopFront(List* lst){
    if (lst == NULL || lst->_head  == lst->_head)
        return;
    struct ListNode* next = lst->_head->_next;
    struct ListNode* nextnext = next->_next;
    
    nextnext->_prev = next->_next;
    lst->_head->_next = nextnext;

    free(next);
    
}

void ListErase(List* lst, struct ListNode* node){
//Cannot delete the head node
    if (lst == NULL || lst->_head == node)
        return;
    //prev, node, next
    struct ListNode* prev = node->_prev;
    struct ListNode* next = node->_next;

    prev->_next = next;
    next->_prev = prev;

    free(node);

}

void ListInsert(List* lst, struct ListNode* node, LDataType val){
    if (lst == NULL)
        return;
    struct ListNode* prev = node->_prev;
    struct ListNode* newNode = createListNode(val);

    //prev newNode node
    prev->_next = newNode;
    newNode->_prev = prev;

    newNode->_next = node;
    node->_prev = newNode;
}

//destroy
ListDestoty(List* lst){
    if (lst){
        if (lst->_head){
            struct ListNode* cur = lst->_head->_next;
            while (cur != lst->_head){
                struct ListNode* next = cut->_next;
                free(cur);
                cur = next;
            }

            free(lst->_head);
        }
    }
}

void test(){
    List lst;
    ListInit(&lst);
    ListPushFront(&lst, 5);
    printList(&lst);
    ListPushFront(&lst, 1);
    printList(&lst);
    ListPushFront(&lst, 2);
    printList(&lst);
    ListPushFront(&lst, 3);
    printList(&lst);
    ListPushFront(&lst, 4);
    printList(&lst);
    ListPopFront(&lst);
    printList(&lst);
    ListPopFront(&lst);
    printList(&lst);
    ListPopFront(&lst);
    printList(&lst);

    /*ListPopBack(&lst);
    printList(&lst);
    ListPopBack(&lst);
    printList(&lst);
    ListPopBack(&lst);
    printList(&lst);
    ListPopBack(&lst);
    printList(&lst);*/
}

int main(){

    test();
    system("pause");
    return 0;
}

The difference and connection between sequential lists and linked lists:

Advantages and disadvantages of sequential lists: Advantages: continuous space, supports random access, high space utilization, not easy to cause memory fragmentation, high efficiency of tail insertion and tail deletion.

Disadvantages: 1. The time complexity of inserting and deleting in the middle or front part is O(N) 2. The cost of increasing capacity is relatively high: apply for copy release

The pros and cons of linked lists (headed bidirectional random linked lists)

Advantages: 1. The time complexity of inserting and deleting at any position is O(1) 2. There is no capacity expansion problem, one insertion creates one space, and the efficiency of inserting and deleting at any position is high

Disadvantages: It is stored in nodes, does not support random access, and has low space utilization, which can easily cause memory fragmentation.

Stacks and Queues

Stack: A special linear table that allows element insertion and deletion operations at only one end. The end where data is inserted and deleted is called the top of the stack, and the other end is called the bottom of the stack. The data in the stack follows the LIFO (last in first out) principle.

Push: The insertion operation of the stack is called push/push/push, and the data is at the top of the stack.

Pop: The deletion operation of the stack is called pop, and the data is also at the top of the stack.

Implementation of stack push operation push---&gt; store elements from the top of the stack

Sequence table: It can be regarded as a tail insertion operation

Linked list: (bidirectional headed circular linked list) The head of the table is regarded as the top of the stack, which is the head insertion, and the tail of the table is regarded as the top of the stack, which is the tail insertion.

Pop operation pop---&gt; remove elements from the top of the stack

Sequence list: the end of the list is regarded as the top of the stack, and it is regarded as a tail deletion operation

Linked list: (bidirectional circular linked list with head) If the head of the list is regarded as the top of the stack, it is head deletion, and if the tail of the list is regarded as the top of the stack, it is tail deletion.

#include<stdio.h>
#include<stdlib.h>

typedef int STDataType;
//The sequence table implements a stack
typedef struct stack{
    STDataType* _data;
    int _size;
    int _capacity;
}stack;

void stackInit(stack* st){
    if (st == NULL)
        return;
    st->_data = NULL;
    st->_size = st->_capacity = 0;
}

void checkCapcacity(stack* st){
    if (st->_size == st->_capacity){
        int newCapcacity = st->_capacity == 0 ? 1 : 2 * st->_capacity;
        st->_data = (STDataType*)realloc(st->_data, sizeof(STDataType)* newCapcacity);
        st->_capacity = newCapcacity;
    }

}

//Push into the stack
void stackPush(stack* st, STDataType val){
    if (st == NULL)
        return;
    checkCapacity(st);
//Tail plug
    st->_data[st->_size++] = val;

}

//Pop out
void stackPop(stack* st){
    if (st == NULL)
        return;
    if (st->_size > 0)
        st->_size--;
}

STDataType stackTop(stack* st){
    return st->_data[st->_size - 1];
}

int stackSize(stack* st){
    if (st == NULL)
        return 0;
    return st->_size;
}

void test(){
    stack st;
    stackInit(&st);
    stackPush(&st, 1);
    stackPush(&st, 2);
    stackPush(&st, 3);
    stackPush(&st, 4);
    for (int i = 0; i < 4; ++i){
        printg("%d", stackTop(&st));
        stackPop(&st);
    }
    printf("n");
}

int main(){
    test();
    system("pause");
    return 0;
}