연결 리스트(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)

저작자표시 비영리 변경금지

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

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

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

	// else 이하 부분 코드

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

	// else 이하 부분 코드

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

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

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

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

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

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

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

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

1.2. 변형된 연결 리스트

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

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

2. 양방향 연결 리스트

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

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

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

자료

블로그의 정보

활동하기

공유하기

다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역