단계별로 Linked List를 구현하기

단계별로 Linked List를 구현하기

2020, Apr 20    

자료구조를 직접 구현할줄 알아야 하는 이유

Linked List(연결 리스트)는 노드들이 순서대로 연결되어 있는 가장 기본적이고 단순한 자료구조입니다.
이 자료구조를 구현하는 방법을 숙지하면 이후에 배우는 Queue, Stack, Hash 과 같은 자료구조를 구현하는데에도 많은 도움이 됩니다.
그러니 꼭 이해하시는걸 추천드립니다.

물론 실제로 연결리스트를 직접 구현하는 일들은 거의 없을 것입니다.
왜냐하면 여려가지 언어에서 이미 구현되어있는 라이브러리를 사용하면 되기 때문입니다.
하지만 직접 구현을 해보면, 연결 리스트에 대해 좀 더 깊게 이해하는 계기가 될 것입니다.
그리고 연결 리스트와 비슷한 자료형 배열(Array)과의 차이점을 이해하시는 데 도움이 될 것입니다.

마지막으로 만약 삼성 SW 역량 테스트 B형 을 준비하신다면
꼭 자료구조를 구현할 줄 알아야 합니다. 그럼 한번 구현해보도록 합시다!

Linked List function

연결 리스트에는 여러 함수가 존재하지만 많이 쓰이는 함수를 위주로 구현해 보겠습니다.
그리고 단계별로 함수를 만들면서 유용한 함수 몇 가지를 추가로 만들어보겠습니다.

  • init: 리스트를 초기화
  • seach: index 위치의 노드를 반환
  • append: 마지막에 값을 추가
  • insert: index 위치에 노드를 연결
  • remove: index 위치 노드를 제거
  • pop: index 위치 노드를 제거하고 값을 반환
  • replace: index 위치의 노드를 값을 변경
  • print: 리스트를 순회면서 값을 출력

노드 만들기

가장 먼저 해야 할 일은 노드 구조체를 만들어 주는 일입니다. 노드는 데이터를 담고 있고,
이전 노드와 그다음 노드를 가리키는 포인터를 가지고 있어야 합니다. 데이터의 형태는 사용자의 필요에 따라 바꿀수 있습니다.

struct Node {
  int data;
  Node* prev;
  Node* next;
};

구현의 편의성과 확장성을 위해 이중 연결리스트로 구현하는 것을 선호합니다.
단일 연결리스트 로 구현하는 경우, 삽입(Insert)이나 값에 접근하는 경우에는 차이가 없지만,
삭제(Delete) 또는 뒤에서부터 값을 순회하는 함수를 구현할 때 구현이 복잡해지는 단점이 있습니다.

그렇기 때문에 이중 연결리스트로 구현하시기를 추천해 드립니다.

연결 리스트 초기화: Initialize

init

구조체를 만든 다음 할 일은 연결 리스트의 head와 tail을 만들고 초기화 해주어야 합니다.

처음에는 어떠한 노드도 존재하지 않기 때문에 head의 다음에는 tail이 오고,

반대로 tail 이전에는 head가 와야 합니다.

따라서 head->next를 tail로 tail->prev를 head로 만들어주고 나머지 방향에는 0으로 초기화 해줍니다.

Node* head = new Node();
Node* tail = new Node();

void init() {
	// head 초기화
	head->prev = 0;
	head->next = tail;
	// tail 초기화
	tail->prev = head;
	tail->next = 0;

	return;
}

마지막 노드에 값을 추가: Append

connect

이번에는 마지막 노드에 값을 추가하는 함수 append를 만들 텐데, 그 이전에 아주 유용한 함수 connect를 먼저 만들어 보겠습니다.

connect가 하는 일은 간단합니다. 현재 노드와 다음 노드(next)를 받아 둘이 연결해주는 함수입니다.

connect 함수를 만들어 놓으면 다음에 구현할 Insert 함수에서도 사용할 수 있습니다.

// next와 node 연결
void connect(Node* node, Node* next) {
	Node* prev = next->prev;
	// node와 next 연결
	node->next = next;
	next->prev = node;
	// node와 prev 연결
	node->prev = prev;
	prev->next = node;
	return;
}

connect 함수가 next 이전에 노드를 추가해주는 함수이기 때문에, append는 정말 간단하게 마지막 노드(tail)에 node를 연결하면서 만들 수 있습니다.

void append(int data) {
	Node* node = new Node();
	node->data = data;
	// 마지막(tail)에 연결
	connect(node, tail);
	return;
}

connect 함수에 이어 두 번째로 유용한 함수 search를 만들어 보겠습니다. search는 index 위치의 노드를 반환하는 함수입니다.
배열로 예를 들면 arr[i]와 비슷한 역할을 하는 함수입니다.

하지만 배열의 경우 arr[i]의 연산 시간 복잡도는 O(C)(상수) 시간인 데 반해,
연결 리스트는 head부터 해당 index까지 링크를 타고 들어가야 하기 때문에 평균 O(N)의 시간이 소요됩니다.

반면 아래에서 다룰 삽입(insert) 또는 삭제(remove)의 연산에서 배열의 경우 빈자리를 하나씩 채워야 하므로 O(N),

연결 리스트는 해당 노드를 연결해주거나 연결을 끊으면 되기 때문에 O(C)(상수) 시간 복잡도를 갖습니다.

Node* search(int index) {
	int pos = 0;
    // head부터 index까지 
	for (Node* iter = head->next; iter != tail; iter = iter->next) {
		if (pos == index) {
			return iter;
		}
		pos++;
	}
    // index out of range
	return 0;
}

해당 위치에 값을 삽입: Insert

search 함수와 connect 함수를 만들어 주었기 때문에 insert(삽입) 함수는 비교적 간단합니다.

Insert func

  1. search로 해당 index의 노드를 찾기
  2. connect로 노드를 연결

여기서 주의할 사항은 만약 index가 연결 리스트의 길이 보다 크다면, 삽입을 할 수가 없습니다.

bool insert(int index, int data) {
    // 노드 찾기
	Node* next = search(index);
	// index out of range
	if (next == 0) {
		return false;
	}
	Node* node = new Node();
	node->data = data;
	// 연결
	connect(node, next);
	return true;
}

해당 위치에 값을 변경: Replace

값을 변경해주는 replace함수도 search로 해당 위치 노드를 찾고 값을 변경해주면 됩니다.

bool replace(int index, int data) {
	Node* node = search(index);
	// index out of range
	if (node == 0) {
		return false;
	}
	node->data = data;
	return true;
}

해당 위치에 값을 제거: Remove

ezgif com-gif-maker

지금까지는 연결리스트에 값을 더해주는 함수를 주로 만들었다면,

이번에는 노드를 제거하는 함수를 만들어 보겠습니다.

값을 연결할 때는 connect 함수가 유용했다면, 연결을 끊어줄 때 유용한 함수는 바로 disconnect 함수입니다.

disconnect 함수는 connect 함수와 반대로 node를 받아서 양방향 연결을 끊어주는 함수입니다.

Disconnect func

  1. next를 prev와 연결
  2. prev를 next와 연결
  3. node의 연결 끊어주기
// 연결 끊는 함수
void disconnect(Node* node) {
  Node* next = node->next;
	Node* prev = node->prev;

	next->prev = prev;
	prev->next = next;
	node->next = node->prev = 0;
}

이제 disconnect 함수로 remove 함수를 만들어보겠습니다.

Remove func

  1. search로 해당 index의 노드를 찾기
  2. disconnect로 노드 연결 끊기
  3. node 제거
bool remove(int index) {
	Node* node = search(index);
	// index out of range
	if (node == 0) {
		return false;
	}
	// 연결 끊기
	disconnect(node);
	delete node;

	return true;
}

해당 위치에 값을 제거하고 반환: Pop

pop 함수는 remove 함수에 data를 따로 저장해서 포인터로 넘겨주는 로직만 추가해주시면 됩니다.

bool pop(int index, int* data) {
	Node* node = search(index);
	// index out of range
	if (node == 0) {
		return false;
	}
	// 연결 끊고 값을 저장
	*data = node->data;
	disconnect(node);
  delete node;
    
	return true;
}

리스트를 순회면서 값을 출력: Print

반대로 값을 출력하고 싶은 경우 reverser를 true로 주면 tail부터 head까지 값을 반대로 출력합니다.

void printList(bool reverse = false) {
	if (reverse) {
		for (Node* iter = tail->prev; iter != head; iter = iter->prev) {
			cout << iter->data << " ";
		}
	}
	else {
		for (Node* iter = head->next; iter != tail; iter = iter->next) {
			cout << iter->data << " ";
		}
	}
	cout << endl;
	return;
}

기능 테스트

이제 만든 기능들을 테스트 해보면,

  1. 연결 리스트 초기화 []
  2. 1 을 리스트에 추가 [1]
  3. 2 을 리스트에 추가 [1, 2]
  4. 3 을 리스트에 추가 [1, 2, 3]
  5. 출력: 1 2 3
  6. 0번째 -1 추가. [-1, 1, 2, 3]
  7. 출력: -1 1 2 3
  8. 2번째 노드 제거 [-1, 1, 3]
  9. 출력: -1 1 3
  10. 반대로 출력: 3 1 -1
int main() {
	init();
	append(1);
	append(2);
	append(3);
	printList();
    // 1 2 3
	insert(0, -1);
	printList();
    // -1 1 2 3
	remove(2);
	printList();
	// -1 1 3
  printList(true);
  // 3 1 -1
}

전체 코드는 github 에서 받아보실수 있습니다 ;)

이상 단계별로 Linked List를 구현하기를 마칩니다.

# 자료구조 # linked list # list # 연결 리스트 # 리스트 # 역량 테스트