[자료구조 및 알고리즘] Lists (C++)

1. 리스트(Lists)란? 📜

---

리스트는 자료(item)의 집합인데요, 각 자료들이 순서(ordered)를 갖고 나열되어 있는 것입니다.

⚠️ 여기서 순서는 정렬(sorting)되어 있다는 뜻은 아닙니다. 위 그림에서 2의 위치는 "1 다음"과 "3 이전"에 위치해 있는데, 이런 상대적인 위치이자 고유한 위치를 "순서를 갖는다"고 이해하면 됩니다.

리스트는 구현 방식에 따라:

• 🟦 Array-based List
• 🔗 Linked List(single / double)

로 나눌 수 있습니다. 그런데, 구현 방식이 달라도 리스트가 제공하는 기능(ADT)은 동일해야 합니다.

2. List ADT(Abstract Data Type) ✨

---

리스트가 어떤 기본 연산을 지원해야 할까요? 📋

• 리스트는 아이템을 삽입(insert)하거나 삭제(remove)함에 따라 크기가 늘어나거나 줄어들 수 있어야 합니다.
• 리스트의 어느 위치에서든 아이템을 삽입하거나 삭제할 수 있어야 합니다.
• 또한 리스트의 각 아이템에 접근할 수 있어야 하며, 이를 통해 아이템의 값을 읽거나 변경할 수 있어야 합니다.
• 우리는 리스트를 생성하거나 초기화할 수 있어야 하며, 현재 위치(curr)에서 다음 또는 이전 요소로 이동할 수 있는 기능이 있으면 유용합니다.

리스트가 어떻게 구현되든 제공되어야 하는 기능을 인터페이스화한 것이 다음과 같습니다.

// List class ADT(Generic)
template <typename T>
class List {
	// 소멸자
	virtual ~List() = default; // 컴파일러가 제공하는 소멸자를 따르겠다는 뜻

	// Remove all contents from the list
	virtual void clear() = 0;

	// Insert "it" at the current location
	// The client must ensure that the list's capacity is not exceeded
	virtual bool insert(const T& it) = 0;

	// Append "it" at the end of the list
	// The client must ensure that the list's capacity is not exceeded
	virtual bool append(const T& it) = 0;

	// Remove and return the current element
	virtual T remove() = 0;

	// Set the current position to the start of the list
	virtual void moveToStart() = 0;

	// Set the current position to the end of the list
	virtual void moveToEnd() = 0;

	// Move the current position one step left, no change if already at beginning
	virtual void prev() = 0;

	// Move the current position one step right, no change if already at end
	virtual void next() = 0;

	// Return the number of elements in the list
	virtual int length() = 0;

	// Return the number of the current element
	virtual int currPos() = 0;

	// Set the current position to "pos"
	virtual bool moveToPos(int pos) = 0;

	// Return true if current position is at end of the list
	virtual bool isAtEnd() = 0;

	// Return the current element
	virtual T getValue() = 0;

	virtual bool isEmpty() = 0;
};

3. Array-based List 🗄️

---

3-1. 배열(array) 🔍

Array-based라고 하는 것은 데이터의 저장 공간이 배열(array)임을 뜻합니다. 우리가 C++에서 arr[10] = { 10, 2, 3, 2,55, 6, 347, 546 ,43253, 52};라고 선언해서 쓰는 것이 바로 배열인데요, 배열은 다음과 같은 특징이 있습니다.

특 징	설명
📏 정적 크기	선언 시 용량이 결정되며, 실행 중에는 크기를 바꿀 수 없습니다.
🧱 연속된 메모리	요소가 메모리상에 순차적으로 배치되어 캐시 효율이 높습니다.
🟰 단일 자료형	모든 요소가 같은 데이터 타입을 가져야 합니다.
⚡ O(1) 인덱스 접근	인덱스를 통해 원하는 위치의 요소에 상수 시간으로 접근합니다.

3-2. 배열에 따른 시간복잡도 ⏱️

리스트를 배열로 구현할 경우, 아이템을 삽입(insert) 혹은 삭제(removal) 시 $O(N)$의 시간복잡도를 갖고, 그 외의 기능은 $O(1)$의 시간복잡도를 갖습니다.

• insert(), removal() : $O(N)$
• Other operations : $O(1)$

왜 그런지 살펴볼까요?

삽입(insert) :

위 그림에서 23을 curr(0번)에 삽입하고자 합니다. 각 아이템들은 연속된 메모리 공간에 할당되어 있고 고정된 위치이기 때문에, 23을 위해서 한 칸씩 뒤로 밀어줘야 합니다.

이렇게 해야 23을 curr 위치에 삽입할 수 있고, 이 동작을 수행하는데 $O(N)$의 시간복잡도가 소요됩니다.

삭제(removal):
삭제도 삽입과 마찬가지로 연속된 공간을 당겨줘야 하기 때문에 $O(N)$의 시간복잡도가 소요됩니다.

curr(1번)의 요소를 삭제해볼까요?

반환을 위해 원래 있던 값을 it에 복사해 둡니다.

그리고 curr 뒤에 요소들을 당겨줘야 합니다. 그래야 13다음에는 20이 되기 때문입니다.

리스트 사이즈를 업데이트하면 삭제가 종료됩니다.

3-3. Array-based List 구현 💻

Array-based List는 어떤 Data를 가져야 할까요?

• 먼저 아이템들을 담을 배열이 필요합니다 -> listArray
• 또한 배열은 정적 크기를 갖기 때문에 최대 사이즈를 정해놓아야 합니다. -> maxSize
• 삽입과 삭제 기능을 위해 현재 몇 개의 아이템들이 있는지 관리하고 있어야 합니다. -> listSize
• 기능을 제공하는 기준인 현재 위치를 갖고 있어야 합니다. -> curr

이제 List ADT를 상속받아 Array-based List Alist를 구현해 봅시다.

// Array based List implementation
#include <iostream>
#include <string>
using namespace std;

template <typename T>
class AList : public List<T> {
	T* listArray;						// Array holding list elements
	static const int DEFAULT_SIZE = 10; // Default size
	int maxSize;
	int listSize;
	int curr;

public:
	// 생성자
	// Create a new list object with maximum size "size"
	AList(int size = DEFAULT_SIZE) {
		maxSize = size;
		listSize = 0;
		curr = 0;
		listArray = new T[size];
	}

	~AList() { delete[] listArray; } // 메모리 반환

	// 모든 값들을 직접 지울 필요가 없다
	void clear() { listSize = 0; curr = 0; } // Simply reinitialize values

	bool insert(const T& it) {
		if (listSize >= maxSize) return false; // insert 불가능
		// 일단 아이템들을 밀어야죠
		for (int i = listSize; i > curr; i--)
			listArray[i] = listArray[i - 1];
		// 그리고 it을 curr에 복사
		listArray[curr] = it;
		// listSize + 1
		listSize++;

		cout << curr << "에 " << it << "이 삽입되었습니다.\n";
		return true;
	}

	// 맨 끝에 "it" 추가
	bool append(const T& it) {
		if (listSize >= maxSize) return false; // append 불가능
		// listSize에 값을 넣으면 되죠
		listArray[listSize] = it;
		// listSize up
		listSize++;

		cout << it << "이 추가되었습니다.\n";
		return true;
	}

	// curr를 삭제하는거임
	T remove() {
		// 예외 처리
		if (curr < 0 || curr >= listSize)
			throw out_of_range("remove() in AList has current of " + to_string(curr) + " and size of "
				+ to_string(listSize) + " that is not a valid element");
		// 반환용
		T it = listArray[curr];
		// array 땡겨야죠
		for (int i = curr; i < listSize - 1; i++)
			listArray[i] = listArray[i + 1];
		// list Size down
		listSize--;

		return it;
	}

	void moveToStart() { curr = 0; }				// Set to front
	void moveToEnd() { curr = listSize; }			// Set to end
	void prev() { if (curr > 0) curr--; };			// Move left
	void next() { if (curr < listSize) curr++; }	// Move right
	int length() { return listSize; }				// Return list size
	int currPos() { return curr; }					// Return current position

	// Set current list position to "pos"
	bool moveToPos(int pos) {
		if (pos < 0 || pos >= listSize)
			return false;
		curr = pos;
		return true;
	}

	// Return true if current position is at end of the list
	bool isAtEnd() { return curr == listSize; }

	// Return the current element
	T getValue() {
		if (curr < 0 || curr >= listSize)
			throw out_of_range("getValue() in AList has current of " + to_string(curr) + " and size of " +
				to_string(listSize) + " that is not a valid element");
		return listArray[curr];
	}
	bool isEmpty() { return listSize == 0; }
};

4. Linked List 🔗

---

4-1. Linked List를 이루는 기본 구조 🧩

array-based list는 배열로 구현했기 때문에, 삽입 혹은 삭제 시 $O(N)$의 시간복잡도를 갖습니다. 이 점을 극복하기 위해, linking field를 추가한 것이 바로 Linked List입니다.

Linked List는 값(value)과 함께 다음 노드를 가리키는 포인터(pointer)를 갖고 있습니다. 이 포인터를 통해 다른 노드들과의 관계가 정의되는 것이지요.

• single linked list : 다음 노드만 가리킴
• doubly linked list : 이전과 다음 노드를 가리킴

잠깐 이 그림을 볼까요?

첫 번째 요소에 접근하기 위해 head라고 하는 포인터(pointer)가 있어야 합니다. 리스트의 마지막 요소에 빠르게 접근하기 위해, 또 append 연산을 빠르게 수행하기 위해, tail이라는 포인터(pointer)가 있어야 합니다. 현재 위치를 가리키는 curr는 마찬가지로 존재해야 합니다.

그런데 위 구조는 문제가 있습니다.

먼저, 리스트가 비어있으면 head, tail 그리고 curr는 가리킬 노드가 없습니다. 또한 코드를 작성할 때 복잡성을 증가시키는 문제가 있는데, 이러한 문제를 모두 해결하는 구조가 바로 다음 그림과 같습니다.

이러한 기본 구조를 바탕으로 Linked List가 정의됩니다.

현재 위치(curr)에 노드를 삽입할 때는 어떤 과정을 거치고, 시간복잡도는 얼마나 될까요?

4-2. Linking에 따른 시간복잡도 💡

Single Linked List에서의 삽입(insert):

현재 위치에 15를 삽입하는 과정을 살펴보겠습니다.

curr 위치에 삽입하기 위해 curr에 있던 값을 밀어야 합니다.

빈 노드를 하나 생성합니다. 그리고 여기에 curr가 가리키는 값을 넣습니다.

빈 노드는 curr가 가리키던걸 가리켜야 하고, curr는 빈 노드를 가리켜야 합니다.

이제 curr에 원하는 값을 대입하면, 삽입(insert)은 끝이 납니다.

배열에서처럼 다른 모든 아이템들을 밀어야 하는 것이 아니라, 단순히 포인터를 복사하기만 하면 순서 관계를 해결할 수 있습니다. 삽입 과정에서는 단순히 몇 번의 값 복사가 일어나기 때문에, 시간 복잡도는 $O(1)$입니다. 삭제도 비슷한 방식으로 이루어집니다.

Doubly Linked List에서의 삽입(insert):

doubly linked list에서도 single에서와 크게 다르지 않습니다. 시간복잡도 또한 $O(1)$이고, 복사해야할 포인터의 개수가 더 많을 뿐입니다.

빈 노드를 하나 생성하고, 이 노드에 입력할 값 it을 넣습니다.

curr의 prev를 빈 노드의 prev로 복사하고, curr의 prev의 next를 빈 노드의 next로 복사합니다.

curr가 빈 노드를 가리키도록 바꿔줍니다.

curr의 next의 prev를 빈 노드를 가리키도록 하고, curr의 prev의 next를 빈 노드를 가리키도록 합니다.

이는 일련의 복사 과정에 불과하고, 시간복잡도는 $O(1)$입니다.

4-3. Single Linked List 구현 📄

각 노드가 value와 pointer를 갖기 때문에 하나의 독립된 구조를 만들어주겠습니다. Link라고 하는 클래스를 정의해서 이 Link 클래스로 노드를 나타냅니다.

template <typename T>
// single linked list : 데이터와 하나의 링크
class Link {
private:
	T v;	        //Value for this node
	Link<T>* pnext; //Point to next node in list

public:
	//생성자
	Link() { pnext = nullptr; }
	Link(Link<T>* inn) { pnext = inn; }
	Link(T it, Link<T>* inn) { v = it; pnext = inn; }

	T element() { return v; }
	T setElement(T it) { return v = it; }
	Link<T>* next() { return pnext; }
	Link<T>* setNext(Link<T>* inn) { return pnext = inn; }

};

다음은 array-based list를 만들 때 사용한 List라는 추상 클래스를 상속받아 LList라는 클래스를 만들어주겠습니다.

template <typename T>
class LList : public List<T> {
public:
	Link<T>* head; // Pointer to list header
	Link<T>* tail; // Pointer to last element
	Link<T>* curr; // Access to current element
	int listSize;  // Size of list
	// 생성자
	LList() {
		tail = new Link<T>;
		head = new Link<T>(tail);
		curr = tail;
		listSize = 0;
	}
	
	// 소멸자
	~LList() {
		while (head != tail) {
			Link<T>* temp = head;
			head = head->next();
			delete temp;
		}
		delete head;
	}

	void clear() {
		// 초기상태로 돌아가도록
		// 가비지 컬렉터가 없기 때문에 명시적으로 메모리 해제 해줘야 함
		while (head != tail) {
			Link<T>* temp = head;
			head = head->next();
			delete temp;
		}
		delete head;

		tail = new Link<T>;
		head = new Link<T>(tail);
		curr = tail;
		listSize = 0;
	}

	bool insert(const T& it) {
		Link<T>* temp = new Link<T>(curr->element(), curr->next());
		curr->setNext(temp);
		curr->setElement(it);
		if (curr == tail) {
			tail = curr->next(); // 초기 상태(curr == tail)에서는 tail도 밀어줘야 함
		}
		listSize++;
		return true;
	}

	bool append(const T& it) {
		Link<T>* temp = new Link<T>(tail->element(), tail->next()); // tail->next() == nullptr
		tail->setNext(temp);
		tail->setElement(it);
		tail = tail->next();
		listSize++;
		return true;
	}

	T remove() {
		if (curr == tail) {
			cout << "빈 리스트\n";
			return false;
		}											
		// curr의 remove는 curr next 노드를 삭제하는 것으로 동작함
		T it = curr->element();						// 삭제할 노드의 value를 리턴하기 위해 복사
		curr->setElement(curr->next()->element());	// curr의 value를 curr next의 value로 덮어씌우기
		Link<T>* temp = curr->next()->next();		// curr next를 해제하기 전에 
		curr->next()->setNext(nullptr);				// curr next의 next 끊어내기
		if (curr->next() == tail)					// curr 다음이 tail이면 tail이 갈 곳 잃으니까 
			tail = curr;
		delete curr->next();						// curr next 노드 해제
		curr->setNext(temp);
		listSize--;
		return it;
	}

	void moveToStart() { curr = head->next(); }
	void moveToEnd() { curr = tail; }

	// O(N)
	void prev() {
		if (head->next() == curr)
			return; // no prev

		Link<T>* temp = head; // temp의 next가 curr일 떄까지 loop
		while (temp->next() != curr) {
			temp = temp->next();
		}
		curr = temp;
	}

	void next() { if (curr != tail) curr = curr->next(); }
	int length() { return listSize; }
	int currPos() {
		int i = 0;
		Link<T>* temp = head->next();
		while (temp != curr) {
			temp = temp->next();
			i++;
		}
		return i;
	}

	bool moveToPos(int pos) {
		if (pos < 0 || pos > listSize)
			return false;

		curr = head->next();
		for (int i = 0; i < pos; i++)
			curr = curr->next();
		return true;
	}

	bool isAtEnd() { return curr == tail; }
	T getValue() { 
		if (curr == tail)
		{
			throw runtime_error("값이 없음");
		}
		return curr->element();
	}
	bool isEmpty() { return listSize == 0; }
};

위 클래스를 테스트하는 main 코드입니다.

#include <iostream>
#include "List.h"
#include "SLList.cpp"

using namespace std;

int main() {
    LList<int> myList;

    // 1. 리스트가 비어있는지 확인
    cout << "리스트가 비어 있는가? " << (myList.isEmpty() ? "Yes" : "No") << endl;

    // 2. 요소 추가 (append & insert)
    myList.append(10);
    myList.append(20);
    myList.append(30);
    cout << "append(10), append(20), append(30) 후 길이: " << myList.length() << endl;

    // 3. 현재 커서 값 확인
    myList.moveToStart();
    cout << "현재 값: " << myList.getValue() << endl; // 10

    // 4. 다음 값으로 이동 후 확인
    myList.next();
    cout << "다음 값: " << myList.getValue() << endl; // 20

    // 5. 중간에 요소 삽입
    myList.insert(15);
    myList.moveToStart();
    cout << "insert(15) 후 리스트: ";
    for (int i = 0; i < myList.length(); i++) {
        cout << myList.getValue() << " ";
        myList.next();
    }
    cout << endl;

    // 6. 요소 삭제 (remove)
    cout << "moveToStart() and remove()\n";
    myList.moveToStart();
    cout << "삭제된 값: " << myList.remove() << endl; // 10 삭제
    myList.moveToStart();
    cout << "삭제 후 리스트: ";
    for (int i = 0; i < myList.length(); i++) {
        cout << myList.getValue() << " ";
        myList.next();
    }
    cout << endl;

    // 7. 위치 이동 확인
    myList.moveToPos(1);
    cout << "moveToPos(1) 후 값: " << myList.getValue() << endl; // 20

    // 8. prev() 테스트
    myList.prev();
    cout << "prev() 후 값: " << myList.getValue() << endl; // 15

    // 9. 마지막 요소까지 이동
    myList.moveToEnd();
    cout << "moveToEnd() 후 커서 위치: " << myList.currPos() << endl; // 마지막 위치

    // 10. 빈 리스트에서 getValue() 시도 -> 예외 확인
    try {
        LList<int> emptyList;
        emptyList.getValue();
    }
    catch (runtime_error& e) {
        cout << "예외 발생: " << e.what() << endl;
    }

    return 0;
}

4-4. Doubly Linked List 구현 📄

doubly linked list는 sigle linked list에서 크게 벗어나지 않습니다. 각 노드가 prev를 향하는 pointer를 갖는 것, 그리고 이로 인한 함수 실행 차이 외에는 다른게 없습니다.

각 노드를 표현하는 Link라는 클래스만 정의해보겠습니다.

template <typename T>
class Link {
private:
	T v;
	Link<T>* pprev;
	Link<T>* pnext;

public:
	//생성자
	Link() { pprev = nullptr; pnext = nullptr; }
	Link(Link<T>* inp, Link<T>* inn) { pprev = inp; pnext = inn; }
	Link(T it, Link<T>* inp, Link<T>* inn) { v = it; pprev = inp; pnext = inn; }

	T element() { return v; }
	T setElement(T it) { return v = it; }
	Link<T>* prev() { return pprev; }
	Link<T>* setPrev(Link<T>* inp) { return pprev = inp; }
	Link<T>* next() { return pnext; }
	Link<T>* setNext(Link<T>* inn) { return pnext = inn; }
};

5. List 비교 ⚖️

List를 구현하는 방식에 따라, 시간과 메모리 사이의 트레이드 오프가 존재합니다. 다음의 표는 이런 특징을 정리하고 있습니다.

참고

https://opendsa-server.cs.vt.edu/ODSA/Books/CS2/html/ListLinked.html#id1