연결 리스트(Linked List) 3

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.

 

1. 원형 연결 리스트(Circular Linked List)

1.1. 원형 연결 리스트의 이해

• 마지막 노드가 첫번째 노드를 가리키게 하면 이것이 원형 연결 리스트가 됨

• 새로운 숫자 1을 머리에 추가하는 경우와 꼬리에 추가하는 경우는 각각 이렇다.
• 서로 연결되어 있기 때문에 머리와 꼬리의 구분이 없다고도 한다.
• 하지만 변수 head가 가리키는 노드가 다르다.

 

1.2. 변형된 연결 리스트

• 기존의 포인터 변수가 머리를 가리키는 방식에서 꼬리를 가리키게 변경
  • 꼬리를 가리키는 포인터 변수 → tail
  • 머리를 가리키는 포인터 변수 → tail→next

 

1.3. 변형된 원형 연결 리스트의 헤더파일

• LNext 함수는 무한 반복 호출이 가능하며 리스트의 끝에 도달할 경우 첫번째 노드부터 다시 조회 가능
• 그리고 삽입 함수를 두 가지로 나눔.
• 원형 연결 리스트의 ADT

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

 

1.4. 변형된 원형 연결 리스트의 구현

• 리스트의 초기화와 노드 삽입
  1. 초기화 
  2. 노드 삽입

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

void LInsert~(List *plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node)); // 새 노드 생성 후 데이터 저장
	newNode->data = data;
	
	if(plist->tail == NULL) // 첫번째 노드 삽입
	{
		plist->tail = newNode; // tail이 새 노드를 가리키게 함
		newNode->next = newNode; // 새 노드 자신을 가리키게 함
	}
	else
	{
		// LInsert와 LInsertFront의 차이..
	}
	
	(plist->numOfData)++;
}

• LInsertFront

// else 이하 부분 코드

newNode->next = plist->tail->next;  // 새 노드와 4가 저장된 노드 연결
plist->tail->next = newNode;  // 2가 저장된 노드와 새 노드 연결

• LInsert

// else 이하 부분 코드

newNode->next = plist->tail->next;
plist->tail->next = newNode;
plist->tail = newNode;  // LInsertFront 함수와의 유일한 차이점

• 데이터 조회

typedef struct _CLL
{
	Node * tail;
	Node * cur;
	Node * before;
	int numOfData;
} CList;

• 구조체의 멤버 cur과 before의 역할은 단순 연결 리스트와 동일

int LFirst(List *plist, Data pdata)
{
	if(plist->tail == NULL)   // 저장된 노드가 없다면
		return FALSE;
		
	plist->before = plist->tail;   // before가 꼬리를 가리켜야 함
	plist->cur = plist->tail->next;  // cur이 머리를 가리키게 함
	
	*pdata = plist->cur->data;  // cur이 가리키는 노드의 데이터 반환
	return TRUE;
}

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;  // cur이 가리키는 노드 데이터 반환
	return TRUE;
}

• 노드의 삭제
  • 삭제는 대부분의 경우 상대적으로 복잡한 편
  • 삭제할 노드의 이전 노드가 삭제할 노드의 다음 노드를 가리키게 한다.
  • 포인터 변수 cur을 한칸뒤로 이동시킨다.
  • 삭제할 노드가 tail인 경우의 예외도 포함시켜 줌

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

 

2. 양방향 연결 리스트

2.1. 양방향 연결 리스트의 이해

typedef struct _node
{
	Data data;
	struct _node * next;  // 오른쪽 노드를 가리키는 포인터 변수
	struct _node * prev;
} Node

• 이 세가지 모델 외의 양방향 연결 리스트는 더 있음.
• 양방향으로 연결되어 있기 때문에 구현이 쉬워지고 오히려 코드는 더 쉬운 측면도 존재함.

2.2. 양방향 연결 리스트 헤더파일

typdef int Data;

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

typedef struct _DLinkedList
{
	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 LPrevios(List *plist, Data * pdata);  // LNext 함수의 반대 방향 노드 참조
int LCount(List *plist);

 

2.3. 양방향 연결 리스트의 구현

• 리스트 초기화와 노드의 삽입

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;  // 새 노드의 next를 NULL로 초기화
	newNode->prev = NULL;         // 새 노드의 prev를 NULL로 초기화
	plist->head = newNode;        // 포인터 변수 head가 새 노드 가리키게 함
	
	(plist->numOfData)++; 
}

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는 단방향 연결 리스트와 차이가 없음

int LFirst(List *plist, Data *pdata)
{
	if(plist->head  == NULL)
		return FALSE;
		
	plist->cur = plist->head  // cur이 첫번째 노드를 가리킴
	*pdata = plist->cur->data // cur이 가리키는 노드의 데이터 반환
	return TRUE;
}

int LNext(List *plist, Data *pdata)
{
	if(plist->cur->next == NULL)
		return FALSE;
		
	plist->cur = plist->cur->next;  // cur을 오른쪽으로 이동
	*pdata = plist->cur->data  // cur이 가리키는 노드의 데이터 반환
	return TRUE;
}

int LPrevious(List *plist, Data *pdata)
{
	if(plist->cur->prev == NULL)
		return FALSE;
		
	plist->cur = plist->cur->prev; // cur을 왼쪽으로 이동
	*pdata = plist->cur->data  // cur이 가리키는 노드의 데이터 반환
	return TRUE; 
}

 

자료

• 윤성우의 열혈 자료구조 (윤성우 저, 2023.10)