[C] 연결리스트(LinkedList)

연결리스트(LinkedList)

---

연결리스트(LinkedList)?

연결리스트는 동적인 자료구조로 배열처럼 메모리에 연속된 공간을 차지하지 않습니다.

---

1. 단순 연결리스트(Simple LinkedList)

노드와 다음링크를 가리키는 링크로 구성

처음 시작을 의미하는 head와 마지막 노드인 tail로 구성

2. 환형 연결리스트(Circular LinkedList)

가장 마지막 노드가 처음의 노드를 가리키는 연결리스트

3. 이중 연결리스트(Doubly LinkedList)

전, 후 노드를 가리키는 링크를 가지는 연결리스트

---

단순 연결리스트 예제

구조체 (key, value, 다음을 가리키는 링크로 구성) 선언

typedef struct _node

{

int key; // key

char *value; // value

struct _node *next; // 다음 노드의 위치

} node;

node *head, *tail; // head, tail

초기화 함수

head 와 tail 초기화

void init_list(void){

head = (node*)malloc(sizeof(node));

tail = (node*)malloc(sizeof(node));

head -> next = tail;

tail -> next = tail;

}

노드 삽입 함수

입력받은 노드의 다음에 삽입

node *insert_list(int key, char *value, node *t){

node *s;

s = (node*)malloc(sizeof(node));

s->key = key;

s->value = value;

s->next = t->next;

t->next = s;

return s;

}

노드 삭제 함수

입력받은 노드를 삭제

int delete_list(node *t){

node *s = head;

while(s->next != tail){

if(s->next==t){

s->next = t->next;

free(t);

break;

}else{

s = s->next;

}

}

}

노드 검색 함수

key를 이용해서 원하는 노드를 검색

node *find_node(int key){

node *s = head->next;

while(s != tail->next){

if(key == s->key){

break;

}else{

s = s->next;

}

}

return s;

}

전체 검색 함수

void findAll(){

node * t = head->next;

printf("#########findAll()########\n");

while(t != tail){

printf("find(%d) = %s , address = %d\n",t->key,find_node(t->key)->value,&t->next);

t = t->next;

}

printf("##########################\n");

}

메인 함수

노드 초기화 후 5개 데이터를 추가하고 2개의 데이터 삭제 후 전체 출력

void main(){

init_list();

insert_list(0,"apple",head);

insert_list(1,"banana",find_node(0));

insert_list(2,"melon",find_node(1));

insert_list(3,"grape",find_node(2));

insert_list(4,"pineapple",find_node(3));

delete_list(find_node(2));

delete_list(find_node(1));

findAll();

}

실행 결과

---

참고 : C로 배우는 알고리즘 (이재규)

---

관련 포스팅

[Data Strcuture] - 트리(Tree)

[Data Strcuture] - 큐(Queue)

[Data Strcuture] - 스택(Stack)

[Data Strcuture] - 연결리스트(LinkedList)