이중연결리스트

이중 연결리스트란 각 노드가 선행 노드와 후속 노드에 대한 링크를 가지는 연결리스트라고 하고 양방향 연결리스트라고도 한다. 즉 앞 뒤로 움직일 수있는 그런 리스트라고 생각하면 된다.

이중 연결리스트는 구조체 선언을 link를 prev와 next로 나눠야 한다.

노드 삽입과 삭제를 할 때는 prev와 next를 모두 바꿔야 하는 점을 주의해야 한다.

또 삽입과 삭제를 할 때 고려해야할 경우가 몇 가지 있다.

#ifndef __MY_LINKED_LIST_
#define __MY_LINKED_LIST_

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

Node* DLL_Create_Node(int newDate);
void DLL_Destroy_Node(Node* node);
void DLL_Append_Node(Node** head, Node* newNode);
void DLL_Print_Linked_List(Node* head);
void DLL_Print_Linked_List_Reverse(Node* tail);
Node* DLL_Get_Node(Node* head, int pos);
void DLL_Remove_Node(Node** head, Node* targetNode);
void DLL_Insert_Node_After(Node* currentNode, Node* newnode);
#endif

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

Node* DLL_Create_Node(int newData) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = newData;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

void DLL_Destroy_Node(Node* node) {
    if (node != NULL) {
        free(node);
    }
}

void DLL_Append_Node(Node** head, Node* newNode) {
    if (*head == NULL) { /*현재 헤드가 비어있다면*/
        *head = newNode;
    }
    else {
        Node* tail = *head;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newNode;
        newNode->prev = tail;
    }
}

void DLL_Print_Linked_List(Node* head)
{
    Node* iter = head;
    int i = 0;
    while (iter != NULL)
    {
        printf("node[%d]:%d", i, iter->data);
        iter = iter->next;
        if (iter != NULL) printf(" <-> ");
        i++;
    }
    printf("\\n");
}

void DLL_Print_Linked_List_Reverse(Node* tail) {
    Node* iter = tail;
    int i = 0;
    while (iter != NULL)
    {
        printf("N[%d]:%d", i, iter->data);
        iter = iter->prev;
        if (iter != NULL) printf(" <-> ");
        i++;
    }
    printf("\\n");
}

Node* DLL_Get_Node(Node* head, int pos) {
    Node* find = head;
    int i = 0;
    while (find != NULL && i < pos) {
        find = find->next;
        i++;
    }
    return find;
}

void DLL_Remove_Node(Node** head, Node* targetNode) {
    if (targetNode->prev == NULL && targetNode->next == NULL) {
        *head = (*head)->next;
        (*head)->prev = NULL;
        DLL_Destroy_Node(targetNode);
    }
    else if (targetNode->prev == NULL) {
        *head = targetNode->next;
        (*head)->prev = NULL;
        DLL_Destroy_Node(targetNode);
    }
    else if (targetNode->next == NULL) {
        targetNode->prev->next = NULL;
        DLL_Destroy_Node(targetNode);
    }
    else{
        targetNode->prev->next = targetNode->next;
        targetNode->next->prev = targetNode->prev;
        DLL_Destroy_Node(targetNode);
    }
}

void DLL_Insert_Node_After(Node* currentNode, Node* newNode) {
    Node* nextNode = currentNode->next;
    newNode->next = nextNode;
    newNode->prev = currentNode;
    nextNode->prev = newNode;
    currentNode->next = newNode;
}

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

int main(void) {
	Node* head = NULL;
	DLL_Append_Node(&head, DLL_Create_Node(15));
	DLL_Append_Node(&head, DLL_Create_Node(31));
	DLL_Print_Linked_List(head);

	Node* temp = DLL_Get_Node(head, 0);
	printf("Get_Node() test: %d\\n", temp->data);
	DLL_Insert_Node_After(DLL_Get_Node(head, 0), DLL_Create_Node(25));
	DLL_Print_Linked_List(head);
	DLL_Remove_Node(&head, DLL_Get_Node(head, 2));
	DLL_Append_Node(&head, DLL_Create_Node(41));
	DLL_Print_Linked_List(head);
	DLL_Print_Linked_List_Reverse(DLL_Get_Node(head, 2));
	return 0;
}

결과

과제에 대한 고찰

이중 연결리스트를 만들면서 삭제 삽입를 구현할 때 많은 어려움을 겪었다. 특히 삭제 할 때는 헤드 일 때 끝일 때 중간에 삽입 할 때 와 같이 많은 경우에 대해서 처리를 해줘야 했다. 그래도 연결리스트의 좋았던 점은 그 노드의 위치만 알고 있다면 이전 노드와 다음 노드로 유동적으로 움직여서 삽입과 삭제를 for를 사용하지 않고 바로바로 처리가 가능했고 for를 쓰더라도 일반 연결리스트보단 적게 사용해서 유용했던것 같다.