[C++ 자료구조] 단일 연결 리스트(Singly Linked List) - 기본

 

https://thewayaboutme.tistory.com/91

c++ singly linked list 단일 링크드 리스트 구현

이 글은 위 블로그 글을 참고하여 작성되었습니다.

 

연결 리스트를 사용하는 이유

여러가지 값들을 저장하고 처리하는 방법 중 가장 대표적인 것은 아마 배열(Array)일 것이다. 그런데 배열의 경우 중간에 있는 원소를 삭제하거나, 값을 삽입할 때 굉장히 비효율적이다. 

만약 아래와 같은 배열이 있다고 가정해보자.

여기서 22를 삭제하려 한다고 하면 22를 지운 뒤

뒤에 있는 원소들을 모두 앞으로 한칸씩 옮겨줘야 한다.

즉 원소가 n개라면 위에서 수행한 작업의 시간복잡도는 O(n)이 된다. (삽입의 경우도 마찬가지) 

이러한 단점을 보완하기 위해 사용하는 것이 바로 연결 리스트이다. 이 글에서는 단일 연결리스트에 대해 다룰 것이다.

 

 

단일 연결 리스트(Singly Linked List)란?

 

단일 연결 리스트는 모든 원소(element)가 데이터, 링크 쌍으로 이루어져 있고, 이 링크(예를들어 포인터)를 통해 뒤 원소와 연결되는 구조이다. 연결 리스트에서 각 원소는 '노드'라고 표현한다. 아래 그림을 보면 직관적으로 이해할 수 있을 것이다.

위에서 단일 연결리스트는 링크(포인터)를 통해 뒤 원소와 연결되는 구조라고 하였다. 즉 노드들이 연결되어 있는 것이다. 그리고 특별히 첫번째 노드는 'head', 마지막 노드는 'tail'이라고 부른다. 그리고 마지막 노드(tail)은 NULL값을 가리킨다. 따라서 단일 연결리스트를 그림으로 나타내면 아래와 같다. 

 

단일 연결 리스트 구현(C++)

단일 연결 리스트는 C++로 일반적으로 아래와 같이 구현한다.

class StringNode { 
private:
	string elem; //원소의 값
	StringNode* next; //다음 노드를 가리키는 포인터
	friend class StringLinkedList; //StringLinkedList의 private원소 접근가능
};

StringLinkedList는 아래와 같다.

class StringLinkedList {
public:
	StringLinkedList(); //빈 리스트 생성
	~StringLinkedList();
	bool empty()const; //리스트가 비었는지 확인하는 함수
	const string& front()const;  //첫번째 원소 return
	void addFront(const string& e); //맨 앞에 원소 추가
	void removeFront(); //맨 앞 원소 제거
private:
	StringNode* head;
};

이제 StringLinkedList의 각 함수를 차근차근 구현해 보자.

 

먼저 생성자와 소멸자이다. 각각 아래와 같이 구현한다.

StringLinkedList::StringLinkedList()
	:head(NULL){} //즉 head==NULL이면 빈 리스트라는 것을 의미한다.
    
StringLinkedList::~StringLinkedList() { while (!empty())removeFront(); }
//empty함수가 true를 리턴할 때 까지  removeFront함수를 실행한다.

이제 위에서 사용한 empty 함수를 구현해 보자. head==NULL이면 빈 리스트라는 점을 이용한다.

bool StringLinkedList::empty()const {
	return head == NULL;
}

첫번째 원소를 리턴하는 front함수는 아래와 같이 구현한다.

const string& StringLinkedList::front()const { return head->elem; }

여기서 .이 아닌 ->를 사용했는데 이는 head 가 포인터이기 때문이다. (StringNode* head;)

.    : 앞에 포인터가 아닌 것(변수와 같은)이 있을 때 사용
-> : 앞에 포인터가 있을 때 사용

 

addFront함수의 구현

 

이제 addFront함수를 구현해 보도록 하자. 맨 앞에 원소를 추가하기 위해서는 아래 세가지 단계를 거쳐야 한다.

1. 새로운 노드 생성(동적할당)
2. 새로운 노드의 next(포인터)가 현재 head값을 가리키도록 함
3. head변수가 새로 생성한 노드를 가리키도록 함

그림으로 보면 더욱 직관적으로 이해할 수 있다.

 

1. 새로운 노드 생성

2. 새로운 노드의 next(포인터)가 현재 head값(파랑색 첫번째 노드)을 가리키도록 함

3. head변수가 새로 생성한 노드를 가리키도록 함

이제 위에서 한 세가지 단계를 코드로 표현하면 아래와 같다.

void StringLinkedList::addFront(const string& e) { //e는 새로 넣을 값(넣고자 하는 값)
	StringNode* v = new StringNode; //1. 동적할당으로  새로운 노드 생성
	v->elem = e;  //새로운 노드에 값 넣기
	v->next = head; //2. 새로 만든 노드가 head값을 가리키도록 함
	head = v; //3. head가 새로 만든 노드를 가리키도록 함
}

 

removeFront함수의 구현

이제 맨 앞 원소를 삭제하는 removeFront함수를 구현해보도록 하자. 삭제의 경우 더욱 간단하다. 만약 앞에서 추가한 주황색 노드를 제거한다고 가정하자.

초기 상태

 

맨 앞 원소를 삭제하기 위해서도 세가지 단계를 거쳐야 한다.

1. head의 값을 임시 변수(일반적으로 old사용)에 저장
2. head의 값을 old의 다음 노드로 변경(head가 두번째 노드를 가리키도록 함)
3. old 삭제

이 과정 역시 그림을 살펴보도록 하자.

 

1. head의 값을 임시변수 old에 저장(첫번째 노드를 가리키는 old변수 생성)

2. head의 값을 old의 다음 노드로 변경(head가 두번째 노드를 가리키도록 함)

3. old삭제

위 과정을 코드로 나타내면 아래와 같다.

void StringLinkedList::removeFront() {
	StringNode* old = head; //1. head의 값을 임시변수 old에 저장(첫번째 노드를 가리키는 old변수 생성)
	head = old->next; //2. head의 값을 old의 다음 노드로 변경(head가 두번째 노드를 가리키도록 함)
	delete old; //3. old삭제
}

 

총정리

 

위에서 작성한 코드들을 모두 모으면 아래와 같이 된다.

#include <iostream>
#include <string>
using namespace std;

class StringNode { 
private:
	string elem; //원소의 값
	StringNode* next; //다음 노드를 가리키는 포인터
	friend class StringLinkedList; //StringLinkedList의 private원소 접근가능
};

class StringLinkedList {
public:
	StringLinkedList(); //빈 리스트 생성
	~StringLinkedList();
	bool empty()const; //리스트가 비었는지 확인하는 함수
	const string& front()const;  //첫번째 원소 return
	void addFront(const string& e); //맨 앞에 원소 추가
	void removeFront(); //맨 앞 원소 제거
private:
	StringNode* head;
};

StringLinkedList::StringLinkedList()
	:head(NULL) {} //즉 head==NULL이면 빈 리스트라는 것을 의미한다.

StringLinkedList::~StringLinkedList() { while (!empty())removeFront(); }
//empty함수가 true를 리턴할 때 까지  removeFront함수를 실행한다.


bool StringLinkedList::empty()const {
	return head == NULL;
}

const string& StringLinkedList::front()const { return head->elem; }

void StringLinkedList::addFront(const string& e) { //e는 새로 넣을 값(넣고자 하는 값)
	StringNode* v = new StringNode; //1. 동적할당으로  새로운 노드 생성
	v->elem = e;  //새로운 노드에 값 넣기
	v->next = head; //2. 새로 만든 노드가 head값을 가리키도록 함
	head = v; //3. head가 새로 만든 노드를 가리키도록 함
}

void StringLinkedList::removeFront() {
	StringNode* old = head; //1. head의 값을 임시변수 old에 저장(첫번째 노드를 가리키는 old변수 생성)
	head = old->next; //2. head의 값을 old의 다음 노드로 변경(head가 두번째 노드를 가리키도록 함)
	delete old; //3. old삭제
}

 

앞에서 배열은 원소의 추가, 삭제가 비효율적이기 때문에 연결 리스트를 사용한다고 한 바가 있다. 연결리스트에서는 원소를 추가, 삭제하는 작업의 시간 복잡도가 O(1)이다. 하지만 특정 원소에 접근하는 경우 시간 복잡도는 O(n)이다.(앞에서부터 차근차근 접근해야 하니까) 따라서 특정 원소에 접근하는 경우에는 배열을 이용하고, 원소의 추가, 삭제가 필요한 경우는 연결리스트를 이용하는 것이 효율적이다.