[자료구조] [6] 리스트

리스트

리스트의 항목들은 순서 또는 위치를 가진다.

리스트도 앞서 공부한 스택,큐,덱 과 같이 항목들이 일렬로 순서대로 들어있는 선형 자료구조.

 

- 스택,큐,덱 과 리스트의 차이?

스택이나 큐에서 자료의 접근은 전단(front)과 후단(rear)로 제한.
-> 즉 새로운 항목을 중간에 삽입 / 중간에 있는 항목 삭제 허용하지 않음

리스트는 임의의 위치에 있는 항목에 대한 연산을 허용. 임의의 위치에서도 요소의 삽입/삭제 가능.
-> 선형 자료구조들 중에서 가장 활용이 자유롭다.

- "연결 리스트"와 "리스트" 용어의 차이

• 리스트 : 특정한 자료구조. 스택,큐에 대응되는 용어
• 연결 리스트 : 어떤 자료구조를 구현하는 "프로그래밍 기법". 배열에 대응되는 용어

 

 

- 리스트의 연산 & 추상자료형 

• insert(pos,item) : 리스트의 어떤 위치에 새로운 항목을 삽입
• delete(pos) : 리스트의 어떤 위치에 있는 항목을 삭제
• get_entry(pos) : 리스트의 어떤 위치에 있는 항목을 반환
• is_empty() : 리스트가 비었는지를 검사
• is_full() : 리스트가 가득 차있는지를 체크 -> 연결리스트로 구현하면 필요X
• size() : 리스트안의 항목의 개수 세기
• 모든 항목 삭제
• find(item) : 리스트에 특정 항목이 있는지 find
• replace(pos,item) : 리스트의 어떤 위치에 있는 항목을 새로운 항목으로 대치

이 외에도 전단이나 후단에 요소를 삽입하거나 삭제하는 연산, 리스트의 모든 요소를 어떤 기준으로 다시 정렬, 두 개의 리스트를 합하는 연산도 가능.

 

 

 

 

연결리스트로 구현한 리스트

배열로 구현하면 저장할 수 있는 요소의 개수를 늘리기 위해 아주 큰 배열을 사용한다면 메모리의 낭비가 심하고,

리스트가 임의의 위치에서도 삽입과 삭제를 해야하므로 많은 항목들을 이동해야 해서 비효율적이다.

 

-> 연결 리스트는 배열과 달리 동적으로 크기가 변할 수 있는 자료에 적합하다.연결리스트를 이용하면 이문제 해결 가능

 

 

- 단순 연결리스트로 구현한 리스트

노드에는 데이터 필드와 링크 필드가 있다.

리스트의 시작을 나타내는 헤드 포인터만 있으면 된다.

노드들은 연속적으로 연결, 마지막 노드의 링크 필드에는 NULL(nullptr)이 저장되어 더 이상 연결된 노드가 없음을 알린다.

 

 

- 연산들

• is_empty()는 head가 NULL인지 검사하면 된다
• get_entry(pos) : 배열에서는 인덱스로 항목들을 바로 참조(O(1))할 수 있지만 연결리스트는 시작노드부터 하나씩 따라가면서 pos번째 노드 찾아야함(O(n)).
• size() : head부터 다음 노드 따라가며 몇개의 노드가 연결되었는지 확인해야 함(O(n)).
• replace(pos, e) : get_entry(pos)로 먼저 노드 찾고, pos번째 노드가 NULL이 아니면 데이터필드 e로 교체.
• find(e) : head 부터 순서대로 모든 노드를 방문하면서 검사해 항목이 e인 노드 찾고 일치하면 반환, 없으면 NULL 반환.
• clear_list() : 리스트를 비우는 연산. 동적 할당된 모든 연결 노드를 해제. 리스트 공백상태 아닐때 까지 맨앞노드 삭제.

 

• insert(pos,item) : 삽입 연산

리스트의 맨 앞에 삽입하는 경우는 삽입할 노드 N에 head를 연결해주고, head를 삽입할 노드 N으로 교체.

만약 중간 pos 위치에 삽입한다면 get_entry(pos-1)로 prev 노드를 찾고 삽입할 노드 N이 뒤의 노드 C를 가리키게 하고, prev 노드 B가 노드 N을 가리키게 한다. (prev가 NULL이면 삽입 불가능 위치) 

이 연산의 시간복잡도는 O(1). 연결리스트 방식의 가장 큰 장점

( 배열을 이용한 리스트에서는 항목의 이동이 필요해 이 연산이 O(n). )

 

 

• delete(pos) : 삭제 연산

중간 pos위치에 있는 노드 B와 C 사이의 N을 삭제한다면, 

삭제할 노드 N을 새로운 임시 노드 removed가 가리키도록 하고,

removed가 NULL이 아닐 경우 노드 B가 C를 가리키게 한다.

그 다음 삭제할 노드가 들어가있는 removed 노드를 반환한 뒤 동적할당 해제.

삭제 연산은 선행 노드를 알면 다음 노드를 삭제하는 것이 매우 효율적이므로 시간 복잡도는 O(1)

(배열을 이용한 리스트는 삭제할 항목이나 선행 항목을 모두 알더라도 항목의 이동이 필요해 복잡도가 O(n))

맨 앞 노드의 삭제는 head를 removed에 복사 후 head가 다음 노드를 가리키게 한 다음 removed를 해제.

 

단순 연결리스트는 삭제 할 노드가 선행 노드의 링크를 가지고 있지 않다. 따라서 삭제 연산을 위해 선행 노드의 링크를 바꿔야 하므로 선행 노드 자체를 알아야 한다. 

-> 이중 연결 리스트는 선행 노드의 링크 필드도 있으므로 삭제 할 노드만 알아도 선행 노드를 쓸 수 있다.

 

* 삭제/삽입 연산 자체의 시간 복잡도는 O(1)
하지만 결국 선행 노드에 접근/탐색해 다음 노드에 삽입/삭제 연산을 해야한다.
탐색연산은 시간복잡도가 O(n)이므로
현실적인 삭제/삽입 연산의 시간 복잡도는 O(n)

 

 

 

- 코드 구현

* 아래 코드에서는 시작 노드를 위해 NODE*, 즉 포인터 head를 사용해 맨 앞의 데이터를 삽입, 삭제 연산할 때 get_entry(pos-1)을 못하기 때문에 예외처리를 해주었다.

하지만 시작 노드를 구조체 NODE 구조체 자체를 사용해 링크 필드를 헤드 포인터로 사용하면 예외처리를 하지 않아도 되 연산이 간단해 진다.

헤드 노드를 사용하면 링크 필드만 사용되기 때문에 데이터 필드가 낭비되지만, 낭비되는 메모리는 크지 않아 무시 가능

#include <iostream>

using namespace std;

typedef int Element;
typedef struct LinkedNode{
	Element data; // 데이터 필드
	LinkedNode* link; // 링크 필드 : 다음 노드 가리킴
}NODE;

NODE* head = nullptr; // 리스트의 맨 앞 == head 포인터

void init_list() {
	head = nullptr; // 공백상태로 만드는 것
}
bool empty() {
	return head == nullptr;
}
NODE* get_entry(int pos) { // pos 위치에 있는 항목을 반환
	if (!empty()) {
		NODE* node = head; // 첫번째 노드부터
		for (int i = 0; i < pos; ++i) { // 순서대로 모든 노드 방문
			node = node->link;
			if (node == nullptr)
				return nullptr;
		}
		return node;
	}
}
int size() {
	 // 첫번째 노드부터
	int cnt = 0;
	for (NODE* node = head; node != nullptr; node = node->link) { // 순서대로 모든 노드 방문
		++cnt;
	}
	return cnt; 
}

void replace(int pos, Element e) {
	NODE* node = get_entry(pos);	// 값을 대체할 노드를 찾아서
	if (node != nullptr)
		node->data = e;
}

NODE* find(Element e) { 
	for (NODE* node = head; node != nullptr; node = node->link) {
		if (node->data == e)
			return node;
	}
	return nullptr;
}

void insertData(int pos, Element e) { // 삽입 연산
	NODE* node = new NODE;
	node->data = e;
	if (pos == 0) { // 가장 앞에 삽입하는 경우 
		node->link = head;
		head = node;
	}
	else { // 리스트 중간 pos 위치에 삽입하는 경우
		NODE* prev = get_entry(pos - 1);
		if (prev != nullptr) {
			node->link = prev->link;
			prev->link = node;
		}
		else {
			node = nullptr;
			delete node;
		}
	}
}

void deleteData(int pos) { // 삭제 연산
	NODE* removed;
	if (pos == 0) { // 가장 앞 원소 삭제하는 경우
		removed = head;
		head = head->link;
	}
	else {  // 리스트 중간 pos 위치 삭제하는 경우
		NODE* prev = get_entry(pos - 1); // 1. pos 위치 전의 prev 노드 정보를 얻는다
		if (prev != nullptr) {
			removed = prev->link; // 2. removed에 prev가 가리키고 있는 삭제할 노드 넣어줌
			prev->link = removed->link; // 3. prev 링크를 삭제할 노드가 가리키고 있는 다음 노드로 변경
			removed = nullptr;
			delete removed;
		}
	}
}


void clear_list() { // 리스트 비우기.동적 할당된 모든 연결 노드를 해제.
	while (!empty())
		deleteData(0); // 리스트 공백상태 아닐때 까지 맨앞노드 삭제.
}



void print_list(const char* msg) {
	printf("%s --> size=%2d : ", msg, size());
	for (NODE* p = head; p != nullptr; p = p->link) // 연결리스트 특성상 가장 최근에 삽입된 데이터부터 출력
		printf("%2d ", p->data);
	printf("\n");
}


void main() {
	init_list();
	insertData(0, 10);
	insertData(0, 20);
	insertData(1, 30);
	insertData(size(), 40); // 해당 시점에서 pos=3에 삽입 -> 20 30 10 40 
	insertData(2, 50);

	print_list("단순연결리스트로 구현한 리스트 삽입 5회");
	
	replace(2, 90);
	print_list("단순연결리스트로 구현한 리스트 교체 1회");
	
	deleteData(2);
	deleteData(size() - 1);
	deleteData(0);
	print_list("단순연결리스트로 구현한 리스트 삭제 3회");

	clear_list();
	print_list("단순연결리스트로 구현한 리스트 clear 후");
}

단순연결리스트로 구현한 리스트 결과

 

---

 

 

- 다양한 형태의 연결 리스트

- 원형 연결 리스트

원형 연결리스트는 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 연결리스트.

마지막 노드의 링크 필드가 NULL이 아닌 첫 번째 노드 주소가 되는 리스트.

->

리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적일 수 있다.

단순 연결리스트는 리스트의 맨 끝까지 진행하여 마지막 노드까지 간 다음에 삽입할 수 있지만,

원형 연결리스트의 헤드 포인터가 실제로는 마지막 노드를 가리키게 하고, 리스트의 첫 번째 노드가 그 다음 노드가 되도록 한다. 그러면 상수 시간 안에 리스트의 끝에 노드 삽입 가능.

 

 

- 이중 연결 리스트

단순 연결 리스트는 후속 노드 찾기는 쉽지만 선행 노드 찾기는 어렵고,

원형 연결 리스트는 선행 노드를 찾으려면 거의 리스트 전체의 노드를 거쳐서 돌아서 찾아야 한다.

->

이중 연결 리스트는 이러한 문제점을 해결하기 위해 만들어진 자료구조

특정 노드에서 양방향으로 자유롭게 움직일 필요가 있을 때 사용.

이중 연결리스트는 하나의 노드가 선행/후속 노드 두 개의 링크를 가지는 리스트.

링크가 양방향이므로 양방향으로 검색 가능.

 

 

- 코드

#include <iostream>

using namespace std;

typedef int Element;
typedef struct DoubleLinkedNode{
	Element data; // 데이터 필드
	DoubleLinkedNode* prev; // 선행 노드
	DoubleLinkedNode* next; // 후속 노드
}NODE;

NODE head; // 헤드 노드

NODE* get_head() {
	return head.next;
}

void init_list() {
	head.next = nullptr; // 공백상태로 만드는 것
}
bool empty() {
	return get_head() == nullptr;
}
NODE* get_entry(int pos) { // pos 위치에 있는 항목을 반환
	
	NODE* node = &head; // 헤드 노드부터(첫번째 데이터 앞에 있다고 치고)
	for (int i = -1; i < pos; ++i) { // 순서대로 모든 노드 방문
		node = node->next;
		if (node == nullptr)
			break;
	}
	return node;
	
}
int size() {
	 // 첫번째 노드부터
	int cnt = 0;
	for (NODE* node = get_head(); node != nullptr; node = node->next) { // 순서대로 모든 노드 방문
		++cnt;
	}
	return cnt; 
}

void replace(int pos, Element e) {
	NODE* node = get_entry(pos);	// 값을 대체할 노드를 찾아서
	if (node != nullptr)
		node->data = e;
}

NODE* find(Element e) { 
	for (NODE* node = get_head(); node != nullptr; node = node->next) {
		if (node->data == e)
			return node;
	}
	return nullptr;
}

void insertData(int pos, Element e) { // 삽입 연산
	

	NODE* before = get_entry(pos - 1);
	if (before != nullptr) {
		NODE* node = new NODE;
		node->data = e;
		node->prev = before;
		node->next = before->next;
		if (before->next != nullptr)
		{
			before->next->prev = node; // 후행 노드의 선행노드로 삽입할 노드 설정
		}
		before->next = node;
	}
	
}

void deleteData(int pos) { // 삭제 연산
	
	NODE* node = get_entry(pos); // 1. 삭제할 노드 get
	if (node != nullptr) {
		if(node->prev != nullptr)
			node->prev->next = node->next;
		if(node->next != nullptr)
			node->next->prev = node->prev;
	}
	
}


void clear_list() { // 리스트 비우기.동적 할당된 모든 연결 노드를 해제.
	while (!empty())
		deleteData(0); // 리스트 공백상태 아닐때 까지 맨앞노드 삭제.
}



void print_list(const char* msg) {
	printf("%s --> size=%2d : ", msg, size());
	for (NODE* p =get_head(); p != nullptr; p = p->next) // 연결리스트 특성상 가장 최근에 삽입된 데이터부터 출력
		printf("%2d ", p->data);
	printf("\n");
}


void main() {
	init_list();
	insertData(0, 10);
	insertData(0, 20);
	insertData(1, 30);
	insertData(size(), 40); // 해당 시점에서 pos=3에 삽입 -> 20 30 10 40 
	insertData(2, 50);

	print_list("단순연결리스트로 구현한 리스트 삽입 5회");
	
	replace(2, 90);
	print_list("단순연결리스트로 구현한 리스트 교체 1회");
	
	deleteData(2);
	deleteData(size() - 1);
	deleteData(0);
	print_list("단순연결리스트로 구현한 리스트 삭제 3회");

	clear_list();
	print_list("단순연결리스트로 구현한 리스트 clear 후");
}

이중 연결리스트로 구현한 리스트 결과도 동일