연결 리스트 (Linked List)

포인터로 다음 노드를 가리켜 차례로 연결된 노드를 표현하는 자료구조.

 

 

특징

• 특정 인덱스를 상수 시간에 접근할 수 없다.
• 동적으로 공간을 만들어서 추가할 수 있다.
• 첫 번째 노드를 가리키고 있는 변수를 헤드 포인터라고 한다.
• 삽입, 삭제가 빠르고 데이터 수정, 조회가 느리다. (삽입, 삭제는 포인터만 바꿔주면 되지만, 조회나 수정은 헤드 포인터에서 해당 노드가 나올 때까지 포인터 연결을 따라가야 한다. 

 

 

종류

• 단순 연결 리스트 : 하나의 방향으로만 연결
• 원형 연결 리스트 : 맨 마지막 노드의 링크 값이 첫 번째 노드를 가리킴
• 이중 연결 리스트 : 각 노드는 자기 앞에 있는 노드의 링크와 뒤에 있는 노드의 링크를 함께 가지고 있다.

 

 

주의점

• 삭제 연산 후 메모리 반납을 잊지 않는다.
• 추가, 삭제등 포인터 연산에서 순서를 잘 지킨다. (엉키면 리스트가 끊기거나 엉뚱한 노드를 가리키게 된다.)

/*
	이중 연결 리스트
    코드 출처 : C언어로 쉽게 풀어쓴 자료구조 / 생능출판 / 천인국, 공용해, 하상호 지음 
*/
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>

typedef int element;
typedef struct DlistNode {
    element data;
    struct DlistNode *llink;
    struct DlistNode *rlink;
} DlistNode;

void init(DlistNode *phead)
{
    phead->llink = phead;
    phead->rlink = phead;
}

void display(DlistNode *phead)
{
    DlistNode *p;
    for(p=phead->rlink; p!=phead; p=p->rlink) {
        printf("<--- | %x | %d | %x | --->\n", p->llink, p->data, p->rlink);
    }
    printf("\n");
}

//new_node를 before노드의 오른쪽에 삽입
void dinsert_node(DlinkNode *before, DlistNode *new_node)
{
    new_node->llink = before;	//new_node의 왼쪽포인터가 before를 가리킨다.
    new_node->rlink = before->rlink;	//new_node의 오른쪽 포인터가 before가 원래 가리키던 오른쪽 노드를 가리킨다.
    before->rlink->llink = new_node;	//before가 원래 가리키던 오른쪽 노드의 왼쪽 포인터가가 new_node를 가리킨다.
    before->rlink = new_node;	//before의 오른쪽 포인터가 new_node를 가리킨다.
}

//removed노드 삭제
void dremove_node(DlistNode *phead_node, DlistNode *removed)
{
    if(removed == phead_node) return;
    removed->llink->rlink = removed->rlink; //removed의 왼쪽 노드가 removed 바로 다음 노드를 가리키게 한다.
    removed->rlink->llink = removed->llink; //removed 바로 다음 노드가 removed가 아닌 removed 바로 이전 노드를 가리키게 한다.
    free(removed); //removed를 가리키는 포인터가 없어졌으므로 반드시 메모리를 반납한다.
}

void main() {
    DlistNode head_node;
    DlistNode *p[10];
    int i;
    
    init(&head_node);
    for(i=0; i<5; ++i) {
        p[i] = (DlistNode *)malloc(sizeof(DlistNode));
        p[i]-> data = i;
        dinsert_node(&head_node, p[i]);
    }
    
    dremove_node(&head_node, p[4]);
    display(&head_node);
}