1. 링크드 리스트 (Linked List)

1. 개요

자료구조의 일종인 링크드리스트는 각 노드당 데이터를 저장하는 데이터필드 영역과 다음 노드를 가리키는 노드 포인터 영역으로 구성된 자료구조이다.
비슷한 방식으로 배열이 있지만 배열은 처음부터 메모리를 할당하고 시작하기 때문에, 링크드리스트에 비해 데이터의 삽입이나 삭제가 어렵다.
반면, 링크드리스트는 노드를 데이터를 삽입할 때마다 메모리를 할당하고 데이터를 이어주는 형식이라 배열에 비해 메모리 낭비가 덜 하다는 장점이 있다.

단일 연결 리스트 (Single LinkedList)

단순 연결 리스트 (Single LinkedList)는 단 방향 연결 리스트로 다음 노드에 대한 참조만을 가지는 가장 단순한 형태의 연결 리스트이다.
단순 연결 리스트는 단 방향이기 때문에 Head 노드의 주소를 잃어버릴 경우 모든 자료들의 접근이 불가능해지므로 안정적인 자료구조는 아니다.

이중 연결 리스트 (Double LinkedList)

이중 연결 리스트 (Double LinkedList)는 양방향 연결 리스트로 각 노드에서 이전 노드, 다음 노드 모두 참조할 수 있는 연결 리스트이다.
이전, 다음 노드의 참조가 모두 가능하므로 탐색에 용이하고, 단순 연결 리스트에서 삭제를 하려면 시간이 오래 걸리는 것에 비해 이중 연결 리스트에서의 노드 삭제는 훨씬 간단하다.
또한, Head 노드와 Tail 노드를 가지고 있으므로 둘 중 하나가 유일되더라도 리스트를 순회할 수 있기 때문에 손상에 강한 편이다.

2. 코드 구현

2-1) 구조체 선언

typedef struct _node Node; // 구조체 노드 형명재지정 struct _node{ // 데이터를 보관할 노드(자기참조 구조체) Node *prev; // 앞 노드를 가리키는 멤버 DataType data; // 데이터 저장 멤버 Node *next; // 뒷 노드를 가리키는 멤버 }; typedef struct _linkedList{ // 리스트 관리 구조체 Node *head; // 헤드포인터 (헤드노드 가리킴) Node *cur; // 특정 작업 시 노드를 가리키기 위한 포인터 Node *tail; // 테일포인터 (테일노드 가리킴) int length; // 실제 데이터노드의 갯수 }LinkedList;

LinkedList 구조체는 리스트 관리 구조체로서, 
1) 순회를 하기 위한 Head, Tail 노드만을 가리키는 노드 포인터와 
2) 현재 노드 가리킴 및 여러 용도로 쓰이는 노드 포인터,
3) 노드의 개수를 저장하는 int형 변수로 이루어져 있다.

---

2-2) 링크드 리스트 초기화

void create(LinkedList * lp) { lp->head = (Node *)malloc(sizeof(Node)); //헤드 노드 생성 assert(lp->head!=NULL); lp->tail = (Node *)malloc(sizeof(Node)); //테일 노드 생성 assert(lp->tail!=NULL); /*head node와 tail node를 연결 함*/ lp->head->prev=lp->head; lp->head->next=lp->tail; lp->tail->prev=lp->head; lp->tail->next=lp->tail; lp->cur=NULL; //cur가 NULL pointer로 초기화 lp->length=0; //데이터 노드의 개수를 0으로 초기화 return ; }

헤드 노드, 테일 노드를 할당 후, 헤드 노드와 테일 노드를 서로 연결해준다.

---

2-3) 노드 추가 (테일 노 드 뒤로)

Node * makeNode(DataType *dataPtr, Node *prev, Node *next) { Node *np; np = (Node *)malloc(sizeof(Node)); //새로운 노드 생성 assert(np!=NULL); np->prev = prev; np->next = next; np->data = *dataPtr; if(prev != NULL) prev->next = np; if(next != NULL) next->prev = np; return np; } ====================================================================================== Node * appendFromTail(LinkedList *lp, DataType *dataPtr) { lp->cur = makeNode(dataPtr, lp->tail->prev, lp->tail); //새로운 노드 생성 assert(lp->cur!=NULL); lp->length++; //데이터개수 1 증가 return lp->cur; }

양방향 연결 리스트에서 노드를 삽입하는 방법은 두 가지가 있다, 첫 번째는 헤드 노드 앞으로 데이터를 삽입하는 법과 테일 노 드 뒤쪽으로 데이터를 삽입하는 방식이다. 
헤드 노드 앞으로 데이터를 삽입하는 방법은 데이터를 다 넣고 출력을 하게 되면 데이터의 순서가 들어온 순서랑 역순이 되므로 여기선, 테일 노 드 뒤로 삽입하는 코드를 썼다.

우선, 첫째로 makeNode 함수를 이용하여 노드를 하나 할당 후, 데이터 개수를 1개 증가시켜준다.
makeNode 함수는 malloc을 통해 메모리를 할당 후, 전달인자로 이전 노드, 다음 노드를 가져와 서로 선을 이어주는 함수이다.

---

2-4) 노드 삭제

void deleteNode (LinkedList *lp, Node *target) { if(target==NULL) return; //삭제할 데이터의 앞,뒤 노드를 연결시킴 target->prev->next=target->next; target->next->prev=target->prev; free(target); // target노드 삭제 lp->length--; // 데이터 개수 1 감소 } ====================================================================================== void destroy (LinkedList *lp) { while(lp->head->next != lp->tail) // 데이터 노드가 있다면 해제 { deleteNode(lp,lp->head->next); // head 노드 바로 뒷 노드를 삭제 } free(lp->head); // head 노드 삭제 free(lp->tail); // tail 노드 삭제 lp->head = lp->cur = lp->tail = NULL; //모든 포인터를 NULL로 초기화 lp->length = 0; //데이터개수 0으로 초기화 return ; }

노드를 삭제하는 함수, 모든 노드를 삭제하는 함수이다.
deleteNode함수는 전달인자로 삭제할 노드 (target)을 받아 target노드의 이전노드와 target노드의 다음노드를 서로 이어준 뒤, target노드를 free함수를 통해 메모리를 해제하는 방식으로 이루어져있다.

destory함수는 우선 헤드 노드와 테일 노드를 삭제 한 후, 나머지 데이터노드들을 순차적으로 메모리 해제해주는 방식이다.

---

2-5) 노드 정렬

void deleteNode (LinkedList *lp, Node *target) void sortList(LinkedList *lp, int (*compare)(DataType *, DataType *)) // 노드 정렬 { Node *tp; Node *target; DataType temp; // swap용 임시변수 lp->cur=lp->head->next; // 첫 데이터 노드를 가리키게 하고 while(lp->cur!=lp->tail) // 맨 뒷 노드까지 검색 { target = lp->cur; tp=lp->cur->next; // cur의 다음 노드를 가리키게 함 while(tp!=lp->tail) { if(compare(&target->data, &tp->data) > 0) { target = tp; } tp=tp->next; } temp = lp->cur->data; lp->cur->data = target->data; target->data = temp; lp->cur=lp->cur->next; } return; }

변수로는 임시 노드 포인터 tp와 정렬할때 바뀜이 되는 대상 임시 노드 포인터 target, 그리고 Data Swap을 위해 필요한 temp변수가 있다.

링크드리스트 관리 구조체의 cur포인터를 헤드노드 뒷 노드 즉, 첫번째 데이터노드를 가리키게 한 뒤, 반복문을 통해 데이터 끝까지 갈 수 있도록 해준다.
여기서, target노드는 현재 cur포인터로 지정해주고 임시 tp포인터는 cur포인터의 다음 노드를 가리키게 한다.
(ex) 45 - 25 - 11 - 5 - 23 의 구조로 이루어져있는 링크드 리스트일때 target을 45, tp를 25로 지정)
compare함수를 통해 비교하고 그것이 참이면 서로 swap해준다.