[Reference] Linked List

1. Node 구조

typedef struct ListNode {
    int data;
    struct ListNode* prev;
    struct ListNode* next;
};

- Double linked list로 기본 데이터 형은 int지만 다른 데이터형 사용시 수정이 필요하다.

 

 

2. Node 생성

ListNode* list_create(int _data) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));

    node->prev = NULL;
    node->next = NULL;

    // strcpy(node->data, _data);
    node->data = _data;

    return node;
}

- Node는 동적할당되며 적절한 초기화가 이뤄진다.
- 만약 data가 문자열이거나 struct형 등일 경우 단순 대입이 아니라 깊은 복사가 이뤄져야 한다.

 

 

3. Node 삽입

ListNode* list_insert(ListNode* _head, ListNode* new_node) {
    ListNode* next = _head->next;

    _head->next = new_node;
    new_node->next = next;
    new_node->prev = _head;

    if (next != NULL) {
        next->prev = new_node;
    }

    return new_node;
}

- head는 Dummy node이고 head->next에 새로운 Node가 삽입된다. (Front insert)

- 새로운 Node는 삽입전 위의 list_create()함수로 만들어 져야 한다.

 

 

4. Node 삭제

int list_erase(ListNode* head, int _data) {
    ListNode* it = head->next;
    int ret = 0;

    while (it != NULL) {
        if (it->data == _data) {
            ListNode* prev = it->prev;
            ListNode* next = it->next;
            ListNode* tmp = it;
            it = it->next;

            prev->next = next;
            if (next != NULL) {
                next->prev = prev;
            }

            // free(data)
            free(tmp);
            ret++;
        }
        else {
            it = it->next;
        }
    }

    return ret;
}

- 시간 복잡도 : O(n)
- 파라미터로 전달된 data와 동일한 값을 가진 모든 Node를 head 처음부터 끝까지 검색해 지운다.
- 만약 Node생성시 data를 깊은 복사했다면 해당노드 삭제시 data부터 소멸시키고 Node를 소멸시켜야한다.

 

 

5. Reference 사용 예시

int main(int argc, char* argv[]) {
    ListNode* head = list_create(NULL);     // (null)<-[head]->(null)

    /* Insert Node */
    ListNode* node1 = list_create(1);	
    list_insert(head, node1);               // (null)<-[head]<->[1]->(null)
    ListNode* node2 = list_create(2);	
    list_insert(head, node2);               // (null)<-[head]<->[2]<->[1]->(null)
    ListNode* node3 = list_create(3);	
    list_insert(head, node2);               // (null)<-[head]<->[3]<->[2]<->[1]->(null)

    /* Erase Node */
    int count = list_erase(head, 2);        // (null)<-[head]<->[3]<->[1]->(null)

    /* Erase all Nodes with head */
    while (head != NULL) {
        ListNode* tmp = head;
        head = head->next;
        free(tmp);
    }

    return 0;
}