Chap 05. 연결 리스트(Linked List) 3 [윤성우의 열혈 자료구조]

*본 내용은 [윤성우의 열혈 자료구조] 책과 강의를 보고 공부하면서 요점 정리한 내용입니다.

Chap 05-1: 원형 연결 리스트

🔳 원형 연결 리스트

✔ 원형 연결 리스트의 이해

• 단순 연결 리스트의 마지막 노드는 NULL을 가리킨다.
  

• 원형 연결 리스트의 마지막 노드는 첫 번째 노드를 가리킨다.
  

✔ 원형 연결 리스트의 노드 추가

1. 머리에 노드 추가
   

2. 꼬리에 노드 추가
   

• 1과 2는 head가 가리키는 노드가 다르지만 노드 연결 순서는 같다.
  원형 연결 리스트에서는 사실상 머리와 꼬리의 구분이 없다.

🔳 변형된 원형 연결 리스트

✔ 원형 연결 리스트의 대표적인 장점

• 단순 연결 리스트처럼 head와 tail 포인터 변수를 각각 두지 않고, 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다.

• 변형된 원형 연결 리스트
  장점을 부각시키기 위해 head보다 tail을 자주 사용한다. 이를 변형된 원형 연결 리스트라고 하고 원형 리스트의 일반적인 모델이다.
  

• 변형된 원형 연결 리스트의 꼬리를 가리키는 포인터 변수는 tail, 머리를 가리키는 포인터 변수는 tail->next이다.

✔ 변형된 원형 연결 리스트의 구현범위

• 조회관련 LFirst: 이전에 구현한 연결 리스트와 기능 동일

• 조회관련 LNext: 원형 연결 리스트를 계속해서 순환하는 형태로 변경
  (원형 연결 리스트는 그 구조상 끝이 존재하지 않는다. 따라서 LNext 함수는 계속해서 호출이 가능하고, 이로 인해서 리스트를 순환하면서 저장된 값을 반환하도록 구현한다.)

• 삭제관련 LRemove: 이전에 구현한 연결 리스트와 기능 동일

• 삽입관련: 앞과 뒤에 삽입이 가능하도록 두 개의 함수 정의

• 정렬 관련: 정렬과 관련된 부분 전부 제거

• 이외의 부분: 이전에 구현한 연결 리스트와 기능 동일

🔳 (변형된) 원형 연결 리스트 구현

✔ 실행을 위해 필요한 파일들

• CLinkedList.h
• CLinkedList.c
• CLinkedListMain.c

• 실행 결과
  1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
  1 3 5
  

✔ 원형 연결 리스트의 헤더파일과 초기화 함수

• 헤더파일

typedef int Data;

// 노드 구조체
typedef struct _node 
{
	Data data;
	struct _node * next;
} Node;

// 원형 연결 리스트 구조체
typedef struct _CLL
{
	Node * tail;
	Node * cur; // 참조 위한 것
	Node * before; // 삭제 위한 것
	int numOfData;
} CList;

typedef CList List;

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);

• 초기화 함수

void ListInit(List * plist)
{
	// 모든 멤버를 NULL(포인터 번수)와 0(int형 변수)로 초기화한다.
    // (cur과 before은 실질적인 초기화는 다른 곳에서 하므로 여기서 초기화하지 않아도 괜찮다.)
	plist->tail = NULL;
	plist->cur = NULL; // 실질적인 초기화는 LFirst에서
	plist->before = NULL;
	plist->numOfData = 0;
}

✔ 삽입

[첫 번째 노드 삽입]
첫 번째 노드는 그 자체로 머리이자 꼬리이기때문에 노드를 뒤에 추가하던 앞에 추가하던 그 결과가 동일하다.

// LInsert & LInsertFront의 공통부분
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 // 두 번째 이후의 노드라면
	{
		/*** 차이가 나는 부분 ***/
	}

	(plist->numOfData)++;
}

[두 번째 이후 노드 머리로 삽입]

// 노드를 머리에 추가
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)++;
}

[앞과 뒤의 삽입 과정 비교]

• 둘의 실질적인 차이점은?
  노드가 저장된 순서의 차이는 없지만, tail이 누구를 가리키는지 차이가 있다.
  LInsertFront 함수 수행 후 tail의 위치만 바꿔주면 꼬리에 추가한 결과가 된다.

[두 번째 이후 노드 꼬리로 삽입]

//노드를 꼬리에 추가
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; // LInsertFront 함수에는 없는 문장. 유일한 차이점.
	}

	(plist->numOfData)++;
}

✔ 조회 LFirst

함수 호출 결과, 삭제 과정을 위해 cur의 왼쪽 노드는 bofore이어야 한다.

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;
}

✔ 조회 LNext

원형 연결 리스트이므로 리스트의 끝을 검사하는 코드가 없다.

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

	plist->before = plist->cur; // before 한 칸 이동
	plist->cur = plist->cur->next; // cur 이동

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

✔ 노드의 삭제

• 더미 노드 기반 연결 리스트의 삭제 과정(복습)
  ∙ 핵심 연산 1. 삭제할 노드의 이전 노드가, 삭제할 노드의 다음 노드를 가리키게 한다.
  ∙ 핵심 연산 2. 포인터 변수 cur을 한 칸 뒤로 이동시킨다.

LData LRemove(List * plist)
{
	Node * rpos = plist->cur;
    LData rdata = rpos->data;
    
	plist->before->next = plist->cur->next; // 핵심연산1
    plist->cur = plist->before; // 핵심연산2
    
    free(rpos);
    (plist->numOfData)--;
    return rdata;
}

• 그림상으로는 두 연결 리스트의 삭제 과정이 비슷해보이나 원형 연결 리스트에는 더미 노드가 없기 때문에 삭제의 과정이 상황에 따라서 달라진다.
  

• 예외적인 상황1
  삭제할 노드를 tail이 가리키는 경우
  tail을 왼쪽으로 위치 조정이 필요하다.(오른쪽은 머리이므로)
• 예외적인 상황2
  삭제할 노드를 tail이 가리키는데, 그 노드가 마지막 노드라면(노드가 머리이자 꼬리일때)

• 원형 연결 리스트 노드 삭제 구현

Data LRemove(List * plist)
{
	Node * rpos = plist->cur; // 아래 if문에서 꼬리인지 확인하기 위해 rpos에 저장
	Data rdata = rpos->data;

	if(rpos == plist->tail)    // 삭제 대상을 tail이 가리킨다면
	{
		if(plist->tail == plist->tail->next)    // 그리고 마지막 남은 노드라면
			plist->tail = NULL;
		else // 마지막 노드가 아니라면
			plist->tail = plist->before; // tail 왼쪽으로 이동
	}
	
    /*** 단순 연결 리스트와 동일한 코드 ***/
	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

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

Chap 05-2: 양방향 연결 리스트

🔳 양방향 연결 리스트

✔ 양방향 연결 리스트의 이해

• 양방향 연결 리스트를 위한 노드의 표현

typedef struct _node
{
	Data data;
    struct _node * next; // 양방향으로 포인터가 필요하다.
    struct _node * prev;
}

✔ 양방향으로 노드를 연결하는 이유

• 언제든 왼쪽 노드를 알 수 있으므로 before가 불필요해진다.
• 오른쪽 노드로의 이동이 용이하다. 양방향으로 이동이 가능하다.
• 위의 코드에서 보이듯이 양방향으로 연결한다 하여 더 복잡한 것은 아니다.

🔳 양방향 연결 리스트 구현

✔ 우리가 구현할 양방향 연결 리스트 모델

• 함께 구현할 리스트의 모델
  
• 난이도가 있는 LRemove 함수를 일단 ADT에서 제외시킨다.
• 대신에 왼쪽 노드의 데이터를 참조하는 LPrevious 함수를 ADT에 추가시킨다.
• 새 노드는 머리에 추가한다.

※ 문제 05-2도 나중에 직접 풀어보자

• 문제 05-2를 통해서 구현을 요구하는 모델
  
• 문제 05-2에서는 LRemove 함수를 정의한다. 그리고 이 문제는 리스트를 마무리 하는데 있어서 여러 가지 의미를 갖는다.

✔ 실행을 위해 필요한 파일들

• DBLinkedList.h
• DBLinkedList.c
• DBLinkedListMain.c

• 실행 결과
  8 7 6 5 4 3 2 1 2 3 4 5 6 7 8
  

✔ 양방향 연결 리스트의 헤더파일

typedef int Data;

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

// 양방향 연결 리스트 구조체
typedef struct _dbLinkedList
{
	Node * head;
	Node * cur; // 참조 위해
	int numOfData;
} DBLinkedList;

typedef DBLinkedList List;

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); // LNext 함수와 반대로 이동함

int LCount(List * plist);

✔ 양방향 연결 리스트의 활용의 예 (main 함수)

int main(void)
{
	// 양방향 연결 리스트의 생성 및 초기화  ///////
	List list;
	int data;
	ListInit(&list);

	// 8개의 데이터 저장  ///////
	LInsert(&list, 1);  LInsert(&list, 2);
	LInsert(&list, 3);  LInsert(&list, 4);
	LInsert(&list, 5);  LInsert(&list, 6);
	LInsert(&list, 7);  LInsert(&list, 8);
    
    // 추가된 이후의 연결 순서
    // head -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

	// 저장된 데이터의 조회  ///////
	if(LFirst(&list, &data))
	{
		printf("%d ", data);

		// 오른쪽 노드로 이동하며 데이터 조회
		while(LNext(&list, &data)) 
			printf("%d ", data);
		
        
        // 왼쪽 노드로 이동하며 데이터 조회
		while(LPrevious(&list, &data))
			printf("%d ", data);
		
		printf("\n\n");
	}

	return 0;
}

실행 결과

8 7 6 5 4 3 2 1 2 3 4 5 6 7 8

✔ 리스트의 초기화

• ListInit 함수의 정의에 참조해야 하는 구조체의 정의

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

• 멤버 cur은 조회의 과정에서 초기화되는 멤버이니 head와 numOfData만 초기화 하면 된다.

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;

	// 아래 문장에서 plist->head는 NULL이다.
	newNode->next = plist->head;
	newNode->prev = NULL;
	plist->head = newNode;

	(plist->numOfData)++;
}

[두 번째 이후 노드의 삽입]
첫 번째 노드의 추가 과정에 덧붙여서, if문이 포함하는 문장이 두 번째 이후의 노드 추가 과정에서는 요구가 된다.

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

	newNode->next = plist->head;
    
    /***추가된 부분***/
	if(plist->head != NULL)
		plist->head->prev = newNode;

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

	(plist->numOfData)++;
}

✔ 데이터 조회

LFirst 함수와 LNext 함수는 사실상 단방향 연결 리스트의 경우와 차이가 없다. 그리고 LPrevious 함수는 LNext 함수와 이동 방향에서만 차이가 난다.

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;
}