연결리스트 C++

 임의 위치에 데이터를 추가/삭제하는 것이 용이한 연결리스트

---

 생각해보자. 배열에서 임의 위치의 데이터를 삭제하고 빈 공간이 없도록 구성하려면 어떻게 해야할까?

 만일 값 3을 삭제한다고 한다면 값만 사라지고 비어있는 공간이 존재한다.

 이 빈공간을 채우는 방법은 크게 두가지이다.

• 우축의 값을 빈공간과 교체하거나
• 빈공간 오른쪽의 값들을 왼쪽으로 밀어서 빈공간을 오른쪽 끝으로 밀어버리기

 첫 번째 방식의 경우, 마지막 값이 위치한 공간만 안다면 손쉽게 해결할 수 있지만 값의 순서가 바뀌어버리는 문제가 있다.[# 마지막 값이 위치한 공간도 모른다면 시간 복잡도는 O(n)에 수렴할 것이다. 일일이 선형으로 다 돌면서 찾아야하니까] 그렇다고 두 번째 방식을 이용하자니 속도가 무조건 O(n)에 수렴한다. 일일이 값을 좌측으로 옮겨주어야하기 때문이다.

 

 이를 코드로 돌려보면 다음과 같다.

# 우측의 값을 빈공간과 교체하기.

int lastIdx; // 값이 존재하는 공간 중 가장 우측의 인덱스
int voidIdx; // 공백 위치
int length;  // 사용하고 있는 공간의 길이
int capacity;// 전체 공간의 길이
int arr[];

arr[voidIdx] = arr[lastIdx];
length--;

# 빈공간을 우측으로 밀어버리기

int arr[];
int length;
int voidIdx;

for(int i = voidIdx; i < length - 1;++i){
	arr[i] = arr[i+1];
}
length--;

 

 

 만일 삭제할 위치만 알고 있다면 빠르게 빈공간을 없애버리는 방법은 없을까 하면서 나온게 이 자료구조일 것이다.[# 정확히는 정적배열의 문제점을 해결하기 위해 나온 자료구조가 아닐까 생각해본다.]

 

 

연결리스트

 연결리스트는 구조체로 구성된다. 연결리스트의 각 요소는 노드 칭해지는 구조체로 처리되며, 기본 구조는 다음과 같다.

struct node{
	struct node* next;
    int value;
};

 다음 요소를 가리킬 수 있도록 자기 자신의 구조체 포인터와 값을 저장하는 공간 총 두개로 구성되는데, 그 다음 요소가 없을경우 next 멤버는 NULL로 처리해 다음이 없음을 알린다.

 

 연결리스트의 가장 큰 장점은 임의 위치에서 공간을 지우고 양쪽의 공간을 이을 수 있다는 점이다. 배열의 경우 값을 삭제하더라도 공간은 유지되기 때문에 선행해서 설명한 방법 등으로 관리를 해주어야하지만, 연결리스트는 n-1의 next 멤버 값에 n의 주소를 n+1의 주소로 변경해주기만 하면 된다.[# 물론 이 과정에서 n번째 요소는 삭제를 해주어야한다. 그렇지 않으면 메모리 누수가 발생한다.]

 

 이미지로 설명하면 다음과 같다.

 이미지처럼 2번 인덱스(값 2를 저장하고 있는 노드)를 삭제하는 경우, 인덱스 1 요소의 nxt 값을 2가 아니라 3으로 설정해주기만 하면 처리가 완료된다.

 때문에 따로 값을 이동시켜야하는 문제가 수정된다.

 

 

메모리 구조

 연결리스트는 메모리 관리 측면에 있어 배열과 그 구조가 굉장히 다르다. 배열의 경우 메모리의 주소가 이어져 있는 선형적 구조를 띄지만, 연결리스트의 경우에는 각 요소의 주소가 제각각이다.[# 물리적으로 가면 메모리는 mmu에 의해 주소가 관리되기 때문에 물리적 주소 위치에서는 배열도 주소가 이어져 있다라는 장담을 할 수 없지만, 프로그램이 받아오는 메모리 주소는 일단 기본적으로 이어져 있다.]

 

구현

 다음은 클래스로 연결리스트를 관리하는 코드이다.

# 코드

#include <iostream>
#include <iomanip>

class LinkedList {
	struct node {
		struct node* next;
		int value;
	};

	struct node* head;

public:
	bool AddValue(int value) {
		struct node* current;
		if (head) {
			current = head;
			while (current->next) {
				current = current->next;
			}
			current->next = new (struct node){nullptr, value};

		}
		else {
			current = new (struct node){nullptr, value};
			head = current;
		}
		return false;
	}
	bool InsertValue(int value, int index) {
		struct node* current = head;
		while (--index) {
			if (current->next) {
				current = current->next;
			}
			else {
				throw "outOfIndex";
			}
		}
		current->next = new (struct node){current->next, value};
		return false;
	}
	bool DeleteIndex(int index) {
		struct node* current = head;
		struct node* parent = head;
		while (index--) {
			if (current->next) {
				parent = current;
				current = current->next;
			}
			else throw "outOfIndex";
		}
		
		parent->next = current->next;
		delete current;
		return false;
	}
	void print() {
		using namespace std;
		struct node* current = head;
		int index = 0;
		cout << "----출력" << endl;
		while (current) {
			cout << setw(3) << index << ": " << current->value << endl;
			current = current->next;
			index++;
		}
	}
public:
	LinkedList() : head{} {
		
	}

	LinkedList(int value) {
		head = new (struct node){};
		head->value = value;
	}
	~LinkedList() {
		struct node* temp;
		while (head) {
			temp = head->next;
			delete head;
			head = temp;
		}
	}
};

int main() {
	LinkedList lnk{};
	lnk.AddValue(3);
	lnk.print();

	lnk.AddValue(30);
	lnk.AddValue(120);
	lnk.print();
	lnk.InsertValue(1, 1);
	lnk.print();
	lnk.DeleteIndex(1);
	lnk.print();

	return 0;
}

 

 

연결리스트의 확장

 본 포스트에서 제공한 예제는 단방향 연결리스트이다. 이름에서 알 수 있듯이 한쪽에서 다른 쪽으로 이동만 가능하다. 즉, 이미 지나온 요소에는 다시 접근할 수 있는 방법이 없다. 따라서 시작 요소의 주소를 항상 기억하고 있어야한다.

 

 때문에, 위 코드에서 보인 것처럼 head 멤버에 접근하는 것보다 get/set 메서드를 생성해 head의 값을 필요에 따라서 읽기와 쓰기를 나누는 것이 더 안정적일 것이라 판단할 수 있다.[# inline 키워드를 이용해 inline 함수로 처리하면 성능 저하의 문제 없이 사용할 수 있으니 참고할 것]

 

 단방향 연결리스트가 있는 것처럼, 양방향 연결리스트가 존재하는데 단방향 연결리스트의 구조에 이전 노드의 메모리 주소를 담을 수 있도록 수정한 것이다.

struct node{
	struct node* next;
    struct node* before;
    int value;
};

 

# index