[자료구조 및 알고리즘] 3. 리스트(Lists)

1. 리스트(Lists)

---

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

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

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

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

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

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)임을 뜻합니다. 배열은 다음과 같은 특징이 있습니다.

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

3-2. 시간복잡도

리스트를 배열로 구현할 경우, 다음의 시간복잡도를 갖습니다.

• 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 : 이전과 다음 노드를 가리킴

null 노드의 필요성

single-linked list에서 첫 번째 요소에 접근하기 위해 head라고 하는 포인터(pointer)가 있어야 합니다.

리스트의 마지막 요소에 빠르게 접근하기 위해, 또 append 연산을 빠르게 수행하기 위해 tail이라는 포인터(pointer)가 있어야 합니다.

현재 위치를 가리키는 curr는 마찬가지로 존재해야 합니다.

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

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

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

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를 구현하는 방식에 따라, 시간과 메모리 사이의 트레이드-오프(trade-off)가 존재합니다. 다음의 표는 이런 특징을 정리하고 있습니다.

참고

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