[자료구조] 연결 리스트 (Linked list)

[자료구조 공부법 -BY 윤성우씨]

 

1. 자료구조의 ADT 정의

2. 정의한 ADT의 구현

3. 구현이 완료된 자료구조의 활용

 

[연결리스트의 종류]

 

• 배열을 기반으로 구현된 리스트
• 동적할당을 기반으로 구현된 리스트
  • 단순 연결 리스트
  • 원형 연결 리스트
  • 양방향 연결 리스트

ADT(추상 자료형) : 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 "기능이 무엇인지" 나열한것
(ex. 리스트 자료구조의 데이터를 저장하는 기능인 LInsert)
▷ 추상 자료형은 사람에 따라서 정의하는 방식이 다르므로 "표준" 이란것이 없다

 

 

[배열을 기반으로 구현된 리스트]

 

<특징>

 → 노드 개념이 없음

 

장점 : 데이터 참조가 쉽다(by 인덱스)

단점 : 배열의 길이가 한정되어 있다, 삭제할때마다 데이터 이동;;

 

▶ ADT 

필요한 기능 : 리스트 초기화, 데이터 저장, 데이터 참조 (LFirst는 첫번째 데이터 참조, LNext는 방금 참조한 녀석의 다음 데이터 참조), 데이터 삭제, 데이터 갯수 반환

void ListInit(List * plist); //리스트 초기화
void LInsert(List * plist, LData data); //데이터 삽입
int LFirst(List * plist, LData * pdata); //첫번째 데이터 반환
int LNext(List * plist, LData * pdata); //현재 가리키는 인덱스의 다음 데이터 반환
LData LRemove(List * plist); //현재 가리키는 인덱스의 데이터 삭제
int LCount(List * plist); // 총 데이터의 갯수

 

▶ 사용 방법

가장 중점적으로 봐야할것은 데이터의 참조 (첫번째 데이터 조회법과 두번째 이후 조회법이 다름)

if(LFirst(&list, &data))    // 첫 번째 데이터 조회
	{
		printf("%d ", data);	
		while(LNext(&list, &data))    // 두 번째 이후의 데이터 조회
			printf("%d ", data);
	}
	printf("\n\n");

 

▶ 구현

 

• 배열기반 리스트를 의미하는 구조체 - 데이터를 저장할 배열, 데이터의 갯수, 현재 가리키는 데이터의 위치(중요)

typedef struct __ArrayList
{
	LData arr[LIST_LEN];
	int numOfData;
	int curPosition;
} ArrayList;

 

• ADT의 구현

void ListInit(List * plist) //데이터의 초기화
{
	(plist->numOfData) = 0;
	(plist->curPosition) = -1;
}

void LInsert(List * plist, LData data) //데이터 삽입
{
	if(plist->numOfData > LIST_LEN) 
	{
		puts("저장이 불가능합니다.");
		return;
	}

	plist->arr[plist->numOfData] = data;
	(plist->numOfData)++;
}

int LFirst(List * plist, LData * pdata) //첫번째 데이터 참조
{
	if(plist->numOfData == 0)
		return FALSE;

	(plist->curPosition) = 0; //LNext와 유일한 차이점
	*pdata = plist->arr[0];
	return TRUE;
}

int LNext(List * plist, LData * pdata)
{
	if(plist->curPosition >= (plist->numOfData)-1)
		return FALSE;

	(plist->curPosition)++; //LFirst와 유일한 차이점
	*pdata = plist->arr[plist->curPosition];
	return TRUE;
}

LData LRemove(List * plist) //알고리즘 중요!
{
	int rpos = plist->curPosition;
	int num = plist->numOfData;
	int i;
	LData rdata = plist->arr[rpos];

	for(i=rpos; i<num-1; i++)
		plist->arr[i] = plist->arr[i+1];

	(plist->numOfData)--;
	(plist->curPosition)--;
	return rdata;
}

int LCount(List * plist)
{
	return plist->numOfData;
}

 

<특징>

LFirst, LNext

→ Return값이 True, False이고 현재 가리키는 값은 * pdata 로 전달함

LRemove(★)

 → 뒤에 저장된 데이터를 한칸씩 앞으로 땡겨서 삭제할 녀석을 덮어씀

 → 삭제된 데이터를 반환

 → curPosition-- 를 통해 삭제한 데이터의 한칸 앞을 가리키게 함

(ex. 맨 마지막꺼 지웠는데 참조위치 한칸 안땡기면 엉뚱한곳 가리킴)

 

 

---

 

[동적할당을 기반으로 구현된 리스트 - 단순 연결 리스트]

 

<특징>

 → 한쪽 방향(화살표 방향)으로만 움직일수 있음

 → 더미노드 있음

 → 정렬기준 설정하는 함수 있음

 → head만 있고 tail은 없음 (한쪽 방향으로만 움직일수 있기 때문)

노드(Node) - 데이터를 담는 그릇 (데이터를 저장할 장소 + 다른 변수를 가리키기 위한 장소)

▶ ADT

필요한 기능 : 리스트 초기화, 데이터 저장 (머리에 추가), 데이터 삭제(cur 위치에서 삭제), 데이터 참조 (LFirst는 첫번째 데이터 참조, LNext는 방금 참조한 녀석의 다음 데이터 참조), 데이터 갯수 반환, 리스트의 정렬 기준 함수 등록

void ListInit(List * plist); // 리스트 초기화
void LInsert(List * plist, LData data); // 데이터 삽입(F나 S 선택)
void FInsert(List * plist, LData data); // 데이터 삽입(앞으로 삽입)
void SInsert(List * plist, LData data); // 데이터 삽입(함수 이용하여 삽입)
int LFirst(List * plist, LData * pdata); // 더미노드 다음 데이터 참조
int LNext(List * plist, LData * pdata); // cur값 다음 데이터 참조
LData LRemove(List * plist); // 데이터 삭제
int LCount(List * plist); // 데이터의 갯수
void SetSortRule(List * plist, int (*comp)(LData d1, LData d2)); // 데이터의 정렬기준

 

<저장방식> 

 

☆머리에 추가

장점 : 포인터 변수 tail이 불필요하다

단점 : 저장된 순서를 유지하지 않는다

 

☆꼬리에 추가

장점 : 저장된 순서가 유지된다

단점 : 포인터 변수 tail이 필요하다 (tail 뒤에 값을 붙여야하기 때문)

 

→ 머리에 추가하는 방식을 대부분 채택

 

<더미노드>

 

→ 데이터의 추가, 삭제, 조회하는 방식에 있어서 첫번째 노드(head)와 나머지 노드의 차이를 없에기 위해 만듬

    (head를 아얘 더미노드로 만들어버림) 

 

 

▶ 구현 

 

• 노드의 구현

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

 

• 연결리스트를 의미하는 구조체

typedef struct _linkedList
{
    Node * head;  //더미노드
    Node * cur;
    Node * before;  //삭제를 돕는 멤버
    int numOfData;
    int (*comp)(LData d1, LData d2);  //정렬의 기준을 등록
} LinkedList;

 

☆ 노드를 삭제할때 가리키는 값을 두개를 두는 이유는 값을 한개만 가리키면 가리키는 값이 삭제되면 그 다음 노드에 접근 하지 못함 (before, cur의 존재 이유)

☆ Node * head, Node * cur 같은 변수들을 지역,전역변수에 두게 되면 list 만들때마다 변수도 더 만들어야함 (최악;;)

 

 

• ADT의 구현 (노드가 다 동적할당으로 이루어져 있음)

void ListInit(List * plist)
{
	plist->head = (Node*)malloc(sizeof(Node));
	plist->head->next = NULL;
	plist->comp = NULL;
	plist->numOfData = 0;
}

void FInsert(List * plist, LData data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = plist->head->next;
	plist->head->next = newNode;

	(plist->numOfData)++;
}

void SInsert(List * plist, LData data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	Node * pred = plist->head;
	newNode->data = data;

	while(pred->next != NULL &&
		plist->comp(data, pred->next->data) != 0)
	{
		pred = pred->next;
	}

	newNode->next = pred->next;
	pred->next = newNode;

	(plist->numOfData)++;
}


void LInsert(List * plist, LData data) // FInsert와 SInsert로 나뉨
{
	if(plist->comp == NULL)
		FInsert(plist, data);
	else
		SInsert(plist, data);
}

int LFirst(List * plist, LData * pdata) // 더미노드의 다음 노드를 가리킴
{
	if(plist->head->next == NULL)
		return FALSE;

	plist->before = plist->head;
	plist->cur = plist->head->next;

	*pdata = plist->cur->data;
	return TRUE;
}

int LNext(List * plist, LData * pdata) // cur노드의 다음 노드를 가리킴
{
	if(plist->cur->next == NULL)
		return FALSE;

	plist->before = plist->cur;
	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;
	return TRUE;
}

LData LRemove(List * plist) // cur노드를 삭제함
{
	Node * rpos = plist->cur;
	LData rdata = rpos->data;

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

int LCount(List * plist)
{
	return plist->numOfData;
}

void SetSortRule(List * plist, int (*comp)(LData d1, LData d2))
{
	plist->comp = comp;
}

 

<특징>

LFirst

 → 더미노드의 다음 노드를 가리킴

SetSortRule

 → 정렬의 기준이 되는 함수를 단순히 초기화

LInsert

 → FInsert(정렬기준 없을때) 와 SInsert(정렬기준 있을때) 로 나눔

FInsert

 → 그냥 앞에서부터 삽입

SInsert(★)

 → Node * pred와 while문을 이용하여 comp함수가 만족하는 값을 찾아서 특정한 위치에 새로운 데이터 삽입

 → while 반복문이 핵심!

(while 반복문)

 pred->next != NULL
 // pred가 리스트의 마지막 노드를 가리키는지
 plist->comp(data, pred->next->data) != 0
 // 새 데이터와 pred의 다음 노드에 저장된 데이터의 우선순위 비교를 위한 함수호출

 → comp 함수는 첫번째 인자가 우선순위 더 높으면 0을 반환한다

 

comp 함수 예시) - 오름차순 정렬

int WhoIsPrecede(int d1, int d2)
{
	if(d1 < d2)
		return 0;    // d1이 정렬 순서상 앞선다.
	else
		return 1;    // d2가 정렬 순서상 앞서거나 같다.
}

 

d1이 데이터이고 d2가 기존에 있는 값이다 d1<d2일때 실행이 되니까 기존에 있는 값이 더 크면 그 이전에 삽입이 이루어진다. 

 

 

---

[동적할당을 기반으로 구현된 리스트 - 원형 연결 리스트]

 

단순 연결 리스트에서 마지막 노드가 첫번째 노드를 가리킴

<특징>

→ 더미노드 없음

→ 리스트의 구성요소에 head 대신에 tail이 있다 → tail->next 가 head이기 때문

→ 앞뒤로 둘다 삽입 가능

 

▶ ADT

필요한 기능 : 리스트 초기화, 꼬리에 노드를 추가, 머리에 노드를 추가, 데이터 참조 (LFirst는 첫번째 데이터 참조, LNext는 방금 참조한 녀석의 다음 데이터 참조), 데이터 갯수 반환

void ListInit(List * plist);
void LInsert(List * plist, Data data); // 꼬리에 노드를 추가
void LInsertFront(List * plist, Data data); // 머리에 노드를 추가
int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
Data LRemove(List * plist);
int LCount(List * plist);

 

▶ 구현

• 노드는 단순 연결 리스트와 동일
• 연결리스트를 의미하는 구조체 (head 대신에 tail)

typedef struct _CLL
{
	Node * tail; // head 대신 tail이 있음
	Node * cur;
	Node * before;
	int numOfData;
} CList;

 

• ADT의 구현

void ListInit(List * plist)
{
	plist->tail = NULL;
	plist->cur = NULL;
	plist->before = NULL;
	plist->numOfData = 0;
}

void LInsertFront(List * plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if(plist->tail == NULL) 
	{
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else
	{
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
	}

	(plist->numOfData)++;
}

void LInsert(List * plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if(plist->tail == NULL) 
	{
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else 
	{
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
		plist->tail = newNode;
	}

	(plist->numOfData)++;
}

int LFirst(List * plist, Data * pdata)
{
	if(plist->tail == NULL)    // 저장된 노드가 없다면
		return FALSE;

	plist->before = plist->tail;
	plist->cur = plist->tail->next;

	*pdata = plist->cur->data;
	return TRUE;
}

int LNext(List * plist, Data * pdata)
{
	if(plist->tail == NULL)    // 저장된 노드가 없다면
		return FALSE;

	plist->before = plist->cur;
	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;
	return TRUE;
}

Data LRemove(List * plist)
{
	Node * rpos = plist->cur;
	Data rdata = rpos->data;

	if(rpos == plist->tail)    // 삭제 대상을 tail이 가리킨다면
	{
		if(plist->tail == plist->tail->next)    // 그리고 마지막 남은 노드라면
			plist->tail = NULL;
		else
			plist->tail = plist->before;
	}

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

int LCount(List * plist)
{
	return plist->numOfData;
}

 

<특징>

LInsert, LInsertFront

 → 처음 만들어진 노드는 그 자체로 머리면서 꼬리이다 (자기 자신을 가르켜야함)

 → 이 두 함수의 유일한 차이점은 tail이 가르키는 노드가 다른것이다

LNext

 → 원형이기 때문에 끊임없이 호출이 가능하다

LRemove

 → ① 삭제할 노드가 tail일 경우와 ② 삭제할 노드가 마지막 노드인 경우를 고려해야함 (더미노드가 없기 때문)

 → 단순 연결 리스트에선 head가 더미 노드 가르켰기 때문에 head를 가르키던게 삭제 될수가 없었음

 

 

 

---

[동적할당을 기반으로 구현된 리스트 - 양방향 연결 리스트]

 

<특징>

→ 노드가 앞뒤를 모두 가리킴

→ 리스트의 구성요소에서 *before이 필요없음 (애초에 before은 한쪽 방향으로만 조회가 가능해서 있었던건데 양방향   연결리스트는 양방향으로 가능)

→ 더미노드를 안넣을수도, head에만 넣을수도, 양쪽 다 넣을수도 있다

 

▶ ADT

필요한 기능 : 리스트 초기화, 리스트 삽입, 데이터 참조 (LFirst는 첫번째 데이터 참조, LNext는 방금 참조한 녀석의 다음 데이터 참조, LPrevious는 방금 참조한 녀석의 이전 데이터 참조), 데이터 갯수 반환

void ListInit(List * plist);
void LInsert(List * plist, Data data);
int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
int LPrevious(List * plist, Data * pdata);
int LCount(List * plist);

 

▶ 구현

 

• 노드의 구현 (노드에 앞뒤를 가리키는 장치가 둘다 있다)

typedef struct _node
{
	Data data;
	struct _node * next;
	struct _node * prev;
} Node;

 

• 연결리스트를 의미하는 구조체 (데이터 조회 목적으로 선언된 멤버가 cur 하나이다!)

typedef struct _dbLinkedList
{
	Node * head;
	Node * cur;
	int numOfData;
} DBLinkedList;

 

• ADT의 구현

void ListInit(List * plist)
{
	plist->head = NULL;
	plist->numOfData = 0;
}

void LInsert(List * plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = plist->head; // 첫번째 노드 추가 상황이면 plist->head가 null이다
	if(plist->head != NULL)
		plist->head->prev = newNode;

	newNode->prev = NULL;
	plist->head = newNode; 

	(plist->numOfData)++;
}

int LFirst(List * plist, Data * pdata)
{
	if(plist->head == NULL)
		return FALSE;

	plist->cur = plist->head;
	*pdata = plist->cur->data;

	return TRUE;
}

int LNext(List * plist, Data * pdata)
{
	if(plist->cur->next == NULL)
		return FALSE;

	plist->cur = plist->cur->next;
	*pdata = plist->cur->data;

	return TRUE;
}

int LPrevious(List * plist, Data * pdata)
{
	if(plist->cur->prev == NULL)
		return FALSE;

	plist->cur = plist->cur->prev;
	*pdata = plist->cur->data;

	return TRUE;
}

int LCount(List * plist)
{
	return plist->numOfData;
}

 

<특징>

LInsert (굉장히 멋있게 코딩이 되어있음!)

 → 노드 추가 과정에서 첫번째 노드 추가 상황과 나머지를 나누어서 생각해야 한다.

 → 첫번째 노드 추가 상황에서 newNode->next = plist->head; 에서 plist->head는 NULL이다

LNext, LPrevious

 → 이 둘의 유일한 차이점은 plist->cur = plist->cur->[prev] or [next] 이다

 

 

---

 

▶ 한번 더 인지할 부분

• 자료구조의 구현과 구현된 자료구조의 활용은 완전히 구분되도록 ADT를 정의해야한다 (STL 쓰는것 같은 느낌 들게)
• 동적할당을 같은 변수에 여러번 하면 할때마다 새로운 주소가 할당된다 (변수 재활용 가능)
• 일반적인 리스트는 LRemove에서 동적할당된 메모리 해제를 책임지지 않기 때문에 return 되는 주소를 이용하여 동적할당 된 메모리를 해제하자