[k-mooc/자료구조] 04. 연결 리스트(Linked List)

04-1. 연결 리스트

https://www.geeksforgeeks.org/dsa/what-is-linked-list/

 

연결 리스트의 원소는 데이터(data)와 다음 원소의 위치에 대한 포인터(link)로 구성된 노드(node)로 지칭한다. 이 때 노드는 배열과 달리 메모리의 랜덤한 위치에 배치되며, 각 노드는 다음 노드를 가리키는 link를 포함한다.

 

	배열	연결 리스트
메모리 공간	연속된 메모리 주소	이산된 메모리 주소(이점)
공간 할당	정적 할당 또는 동적 할당	동적 할당
접근 경로	첫 번째 원소의 주소를 통해 접근	첫 번째 원소의 주소를 통해 접근
접근 방법	인덱스 (`a[i]`)	포인터 (`a` → link)
접근 방식	Random access(이점) 원소의 위치와 접근 시간 간 연관성 없음 (배열의 첫 번째 원소와 배열의 마지막 원소 각각에 대한 접근 시간은 같음)	Sequential access 원소에 접근하는 시간이 원소의 위치에 따라 결정 (첫 번째 원소는 바로 접근할 수 있으나, 마지막 원소는 각 원소의 링크를 차례차례 타고 접근)

 

정의

//C언어 - struct + typeof 정의
typeof struct _node node;
struct _node {
	char ats[3];
	node *link;
}

//C++ - class 정의
class node {
	char ats[3];
	node *link;
}

 

 

04-2. 단일 연결 리스트(Singly Linked List / Chain)

https://www.geeksforgeeks.org/dsa/singly-linked-list-definition-meaning-dsa/

//단일 연결 리스트의 노드 정의
class node {
	data_type item;
	node *link;
}

//원소는 저장하지 않고 첫 번째 노드만 가리키는 head node를 추가로 사용하기도 한다.
class hnode {
	node *link;
}

단일 연결 리스트의 노드는 내가 저장하고자 하는 데이터와 다음 노드를 가리키는 링크 조합으로 선언된다.

 

연산

생성

원소가 없는 연결 리스트를 생성

void main() { hnode first; }

 

검색 (시간 복잡도: \(O(n)\))

찾는 원소(key element)를 저장하고 있는 노드의 포인터를 리턴하며, 연결 리스트에서는 이진 검색은 허용되지 않고 선형 검색만 가능하다.

//HAT이라는 원소를 검색 → HAT을 저장하는 노드를 가리키는 포인터 리턴
void main() { node *temp = first.search("HAT"); }

검색 과정:

1. `hnode`에서 검색 시작: 첫 번째 노드에서 시작
2. 각 노드에서 검색: 검색하는 값을 가진 노드를 검색

코드로 구현하면:

//(1) 연결 리스트에서의 검색 (while문)
node *curr = this;
while (curr != NULL) {
	if(curr->item == key) return **curr**; //검색하는 값을 찾았으므로 리턴
	curr = curr->link;
}

//(2) 연결 리스트에서의 검색 (for문)
for(node *curr=this; curr!=NULL; curr=curr->next) {
	if(curr->item == key) return curr; //검색하는 값을 찾았으므로 리턴
}

//(3) [비교] 배열에서의 검색
for(int i=0; i<n; i=i+1) {
	if(list[i]==key) return list[i]; //검색하는 값을 찾았으므로 리턴
}

 

추가 (시간 복잡도 \(O(n)\))

추가할 데이터를 저장하는 새로운 노드를 연결 리스트에 삽입한다.

1. 데이터를 추가할 적절한 위치를 찾는다.
2. 데이터를 저장할 새로운 노드를 생성한다.
3. 새로운 노드가 연결 리스트에 포함되도록 링크를 갱신한다.

코드로 구현하면:

void node::insert(data_type key) {
	/*
		[처리해야 할 예외]
		1. 첫 번째 노드 앞에 추가할 경우
		2. 텅 빈 리스트에 처음으로 추가할 경우
		3. 마지막 노드 뒤에 추가할 경우
		4. ?
	*/

	//1.
	node *curr = this;
	while(curr->link != NULL) {
		**if(curr->link->item > key) break;** //**새로운 원소보다 더 큰 원소 앞**에 있는 원소에서 중지
		curr = curr->link;
	}
	
	//2.
	node *nnode = new node;
	nnode->item = key;
	
	//3.
	nnode->link = curr->link;
	curr->link = nnode;
}

 

제거 (시간 복잡도 \(O(n)\))

리스트로부터 원하는 원소의 연결을 해제하여 리스트에서 그 원소를 삭제한다.

1. 제거할 원소를 찾는다.
2. 링크를 갱신하여 제거할 원소를 리스트에서 분리한다.
3. 제거된 노드의 메모리를 해제한다(`free`).

코드로 구현하면:

void node::delete(data_type key) {
	/*
		[처리해야 할 예외]
		1. 첫 번째 노드를 제거할 경우
		2. 텅 빈 리스트에서 제거할 경우
		3. 마지막 노드를 제거할 경우
		4. ?
	*/

	//1.
	node *curr = this;
	while(curr->link != NULL) {
		**if(curr->link->item == key)** break; //**제거하고자 하는 원소의 앞**에서 중지 (제거 원소를 가리키고 있는 원소를 찾음)
		curr = curr->link;
	}
	
	//2.
	node *dnode = curr->link;
	**curr->link = dnode->link; //링크 갱신**
	
	//3.
	free(dnode);
}

 

 

04-3. 이중 연결 리스트(Doubly Linked List)

https://www.geeksforgeeks.org/dsa/doubly-linked-list-meaning-in-dsa/

각 노드가 다음(next, rlink)노드를 가리키는 link와 이전(prev, llink)노드를 가리키는 link를 동시에 가지고 있다.

//이중 연결 리스트의 노드 정의
class node {
	data_type item;
	node *llink, *rlink;
}

//원소는 저장하지 않고 첫 번째 노드만 가리키는 head node를 추가로 사용하기도 한다.
class hnode {
	node *link;
}

 

연산

추가 (시간 복잡도 \(O(n)\))

추가할 데이터를 저장하는 새로운 노드를 연결 리스트에 삽입한다.

1. 데이터를 추가할 적절한 위치를 결정한다.
2. 데이터를 저장할 새로운 노드를 생성한다.
3. 새로운 노드가 연결 리스트에 포함되도록 링크를 갱신한다.

코드로 구현하면:

void node::insert(data_type key) {
	/*
		[처리해야 할 예외]
		1. 첫 번째 노드 앞에 추가할 경우
		2. 텅 빈 리스트에 처음으로 추가할 경우
		3. 마지막 노드 뒤에 추가할 경우
		4. ?
	*/

	//1.
	node ***curr** = this;
	while(curr->rlink != NULL) {
		**if(curr->rlink->item > key) break;** //**새로운 원소보다 더 큰 원소 앞**에 있는 원소에서 중지
		curr = curr->rlink;
	}
	
	//2.
	node *nnode = new node;
	nnode->item = item;
	
	**//3. 링크 갱신

	//3-1. rlink 방향 (뒤 노드를 지칭)
	nnode->rlink = curr->rlink;
	curr->rlink = nnode;
	
	//3-2. llink 방향
	nnode->llink = curr;
	nnode->rlink->llink = nnode;**
}

 

제거 (시간 복잡도 \(O(n)\))

리스트로부터 원하는 원소의 연결을 해제하여 리스트에서 그 원소를 삭제한다.

1. 제거할 원소를 찾는다.
2. 링크를 갱신하여 제거할 원소를 리스트에서 분리한다.
3. 제거된 노드의 메모리를 해제(`free`)한다.

코드로 구현하면:

void node::delete(data_type key) {
	/*
		[처리해야 할 예외]
		1. 첫 번째 노드를 제거할 경우
		2. 텅 빈 리스트에서 제거할 경우
		3. 마지막 노드를 제거할 경우
		4. ?
	*/

	//1.
	node *curr = first;
	while(curr->rlink != NULL) {
		**if(curr->rlink->item == key)** break; //**제거하고자 하는 원소의 앞**에서 중지 (제거 원소를 가리키고 있는 원소를 찾음)
		curr = curr->rlink;
	}
	
	**//2. 링크 갱신
	node *dnode = curr->rlink;
	curr->rlink = dnode->rlink; 
	curr->rlink->llink = dnode->llink;**
	
	//3.
	free(dnode);
}