[자료구조] 연결리스트 간단한 구현

[서론]

 

연결리스트에 대해 학습하고 간단하게 c언어로 구현해서 구조파악을 해보겠습니다.

연결리스트는 자료구조의 일종입니다.

 

우선 리스트에 대해 간단히 설명하면, 리스트는 항목들 간에 순서가 있는 자료구조입니다.

예를들어, 한글자음(ㄱ,ㄴ,ㄷ,....,ㅎ) 또는 요일(월요일,화요일,....,일요일) 등을 순차적으로 나열한 자료구조가 리스트라고 볼 수 있죠.

 

리스트의 구현 방법에는 배열을 이용한방법(vector),과 연결리스트를 이용한 방법(linked-list)이 대표적입니다.

그 중에서도 연결리스트는 배열을 이용한 방법보다 구현은 복잡하지만 새로운 자료의 삽입,자료의 삭제에 보다 유용하고,

메모리 동적할당을 사용하기때문에 크기에 제한이 없다는 장점이 있습니다.

 

[본론]

우선 연결리스트를 구현하기위해서 node의 개념부터 알아야하는데, 노드(node)는 데이터필드와 링크필드로 구성되어 있습니다.

노드의 데이터필드에는 말그대로 데이터가 들어가게 되고 링크필드에는 다음노드, 이전노드 등 노드들 간의 연결을 위해 필요한 부분입니다.

링크필드는 포인터 형식으로 다음노드,이전노드등 특정 노드의 주소값을 넣는 방식으로 구현합니다. 

서론에서 언급한 연결리스트의 특징중에서 동적할당을 한다는 것은 이 노드들을 동적할당한다는 것인데 동적할당을 통해 필요할 때마다 새롭게 노드 선언을 해주어야 하고 이렇게 함으로써 배열(정적할당을 통해 미리 메모리를 할당해둠) 보다 메모리 낭비를 최소화 할 수 있게되는 것입니다.

바로 구현해보면,

 

 

 

#include<stdio.h> //전처리기

#include<stdlib.h>

 

typedef struct node { //node 구조체 타입선언

int data;

node*link;

}*node1,*node2,*head;

 

 

 

이런식으로 노드들을 선언해서 node1과, node2를 만듭니다. 헤드는 보통 리스트가 순서가 있는 자료구조라고 하였는데 이 순서의 첫번째를 가르치는 노드를 선언하기 위해 만듭니다.

 

 

 

void main() {

 

node *node1 = (struct node*)malloc(sizeof(node));

 

node *node2 = (struct node*)malloc(sizeof(node));

 

node1->data = 10;

 

node2->data = 20;

 

 

node1->link = node2;

 

node2->link = NULL;

 

node *head = node1;

 

 

printf("node1->data = %d\n", node1->data);

 

printf("node2->data = %d\n", node2->data);

 

printf("node1->link = %d\n", node1->link);

 

printf("node2->link = %d\n", node2->link);

 

printf("head->data = %d\n", head->data);

 

printf("head->link = %d\n", head->link);

 

}

 

 

메인부분입니다. 구조체로 만든 node1,node2에 동적으로 메모리 할당을 malloc()을 사용해서 실제로 할당해주고

 

node1->data = 10;

 

node2->data = 20;

 

이렇게 각노드의 데이터 필드에 10,20을 넣었습니다.

 

원하는 구조는 node1이 헤드노드가 되고, node1과 node2가 연결된 연결리스트를 원하기 때문에, node1->link가 node2의 주소값을 가르키면 되겠죠.

 

구현한 연결리스트에 node1과 node2밖에 없기때문에 마지막노드(node2)의 링크필드는 null값으로 줍니다. (단순연결리스트라서 이렇게합니다. 원형연결리스트는 마지막 노드 링크필드를 헤드의링크로 줘서 앞부분과 다시 연결합니다.)

 

헤드노드는 node1로 넣어주면 됩니다.

 

 

 

결과값입니다. node1의 데이터필드엔 10이 들어가있고 node2의 데이터필드에는 20이 들어가있습니다.

node1의 링크필드에는 node2의 주소값이 들어가있겠죠. node2의 링크필드에는 null값이 들어가고

head는 node1을 넣었기때문에 node1과 똑같이 나옵니다.

 

[결론]

 

이제 단순연결리스트를 다공부했습니다. 여기서 node1과 node2사이에 노드삽입을 하고싶을 경우, 위에 구조체에서 node3을 추가하고 node1,2,3의 링크필드를 수정해주면 됩니다. 맨 앞부분에 삽입(즉,node1대신 3,1,2의 순서로 만듬)일 경우 헤드를 node3을 주면되겠죠. 삭제는 더 단순합니다. node1,2,3의 순서인 연결리스트중 2를 삭제하고 싶은경우 1의 링크필드를 2의 링크필드로 넣어주고 2의 동적할당을 풀어줘버리면 되겠죠.

즉, node1->link = node2->link; 이런식으로 구현할 수있습니다. 링크2의 링크필드에는 node3의 주소값이 들어가있기 때문입니다.

 

정리하면, 연결리스트는 리스트중 삽입,삭제 등이 간편한 자료구조라고 볼 수 있고, 삽입삭제는 node의 링크필드 값을 변경하므로써 구현 가능합니다.