[자료구조] 링크드 리스트

링크드 리스트

: 어떤 노드를 저장할 때 그 다음 순서의 자료가 있는 위치를 포함시키는 상식으로 자료를 저장 

<파이썬 알고리즘 인터뷰>, p.199, 책만, 2020

단일 링크드 리스트(singly linked list)

노드

: 각각의 노드가 값과 다음 노드를 가리키는 포인터 next를 저장한다. next 참조를 통해 한 노드에서 다른 노드로 이동하는 것을 링크 연결하기(link hopping) 또는 포인터 연결하기(pointer hopping)라고 한다. 링크드 리스트의 제일 처음과 마지막 노드를 각각 그 리스트의 head와 tail이라 부른다. null값을 참조하는 next 값을 가진 node가 tail이다.

배열과 마찬가지로 단일 링크드 리스트도 특정 순서로 원소들을 저장하며, 이 순서는 next 링크의 연결로써 결정된다. 배열과 다른 점은 단일 링크드 리스트는 미리 선언되어 고정된 크기를 갖는 것이 아니다! 노드를 추가하거나 삭제함으로써 사이즈를 재조정할 수 있다.

class StringNode { // 문자열 리스트의 노드
private:
    string elem; // 원소값
    StringNode* next; // 리스트의 다음 항목
        
    friend class StringLinkedList; //StringLinkedList에서 이 노드의 private 멤버에 접근할 수 있게 하기 위해 friend로 선언
};

class StringLinkedList { // 문자열의 링크드 리스트
public:
    StringLinkedList() { // 빈 리스트 생성자
        head(null);
    }
    ~StringLinkedList() { // 소멸자
    	while (!empty()) removeFront();
    }
    bool empty() const { // 리스트가 비어있는지
    	return (head == NULL);
    }
    const string& front() const { // 제일 앞의 원소를 얻음
    	return head->elem;
    }
    void addFront(const string& e) { // 리스트의 제일 앞에 추가
    	StringNode* v = new StringNode; // 새로운 노드 생성
        v->elem = e; // 데이터 저장
        v->next = head; // 지금 데이터를 새 노드의 뒤에 저장
        head = v; // 이제 맨 앞(head)는 v
    }
    void removeFront() { // 제일 앞의 리스트 항목 삭제
        StringNode& old = head; // 현재 head를 old라는 노드에 저장
        head = old->next; // head가 원래 head의 다음을 가리킴
        delete old; // 이전 head 삭제
    }
private:
	StringNode* head; // 리스트의 헤드를 가리키는 포인터
}

=> 단일 링크드 리스트는 마지막 노드를 삭제하기 어렵다(head에서 멀리 있는 노드를 지우는 것에 시간이 많이 소요된다)!! 

 

이중 링크드 리스트(doubly linked list)

노드

: 앞 방향과 반대 방향 등 양 방향으로 탐색을 가능하게 해주는 링크드 리스트! 원소 멤버 이외에 리스트의 다음 노드와 이전 노드를 각각 가리키는 next와 prev 링크를 가진다.

=> 어느 위치에서든 효율적인 삽입 및 제거를 포함한 다양한 빠른 업데이트 연산 제공!!

이중 링크드 리스트의 양 끝에 특별한 노드들을 추가하는 것이 좋다!(리스트의 head 앞에 header 노드, tail 다음에 trailer 노드 -> 프로그래밍을 단순화할 수 있음) 이 노드들은 어떠한 원소도 저장하지 않는다. 얘네들을 더미 or 센티널 노드라고 함 -> 리스트의 첫 번째와 마지막 노드들에 빠른 접근이 가능하다!

이중 링크드 리스트에 어떤 노드를 삽입해보자!

c라는 원소를 가지고 있는 p 뒤에 q라는 노드를 추가해보자! p 이전에 위치한 원소 b를 갖는 노드를 r이라고 하자.

r 노드의 next에 q를 연결하고, q의 prev에는 r 노드를 연결하고

q의 next에 p를 연결하고, p의 prev에는 q를 연결하면 된다!!

이렇게!!!

삭제는 어떻게 하냐!!! q를 삭제한다고 하자. 마찬가지로 원소 b를 갖는 노드를 r이라고 하자.

그러면 p의 prev에 r을 연결하고 r의 next에 p를 연결한 후 q 노드를 없애버리면 된다!!

typedef string Elem; // 리스트의 원소 타입! string 말고 자유롭게 ㄱㄱ

class DNode { // 이중 링크드 리스트 노드
private: 
    Elem elem; // 노드 원소 값
    DNode* prev; // 리스트의 이전 노드
    DNode* next; // 리스트의 다음 노드
    friend class DLinkedList; // DLinkedList가 DNode의 private 멤버에 접근하는 것을 허용
};

class DLinkedList { // 이중 링크드 리스트
public: 
	DLinkedList() { // 생성자
    	header = new DNode; // 센티널들을 만듦
        trailer = new DNode;
        header->next = trailer; // 일단 빈 노드니까 서로를 가리키도록 함
        trailer->prev = header;
    }
    ~DLinkedList() { // 소멸자
    	while(!empty()) removeFront(); // 센티널들을 제외한 모든 노드 삭제
        delete header; // 센티널들 삭제
        delete trailer;
    }
    bool empty() const { // 빈 리스트인지 확인
    	return (header->next == trailer;) // 헤더의 next가 trailer면 빈 리스트
    }
    const Elem& front() const { // 가장 앞의 원소를 얻음
    	return header->next->elem;
    }
    const Elem& back() const { // 가장 뒤의 원소를 얻음
    	return trailer->prev->elem;
    }
    void addFront(const Elem& e){
    	add(header->next, e); // 원래 헤더가 가리키고 있었던 맨 앞의 노드 전에 e를 가진 새 노드를 추가
    }
    void addBack(const Elem& e) {
    	add(trailer, e); // 트레일러 앞에 e값을 가진 새 노드를 추가하면 이게 맨 마지막 노드가 됨
    }
    void removeFront() {
    	remove(heder->next);
    }
    void removeBack() {
    	remove(trailer->prev);
    }
private:
	DNode* header; // 리스트 센티널
    DNode* trailer; 
protected:
	void add(DNode* v, const Elem& e) { // v 전에 새로운 노드 추가
    	DNode* u = new DNode;
        u->elem = e; // 원소로 e를 가지는 새로운 노드를 생성
        u->next = v; // 새로운 u 노드의 다음에 v를 연결
        u->prev = v->prev; // 원래 v 이전에 있던 노드를 u 전으로 연결
        v->prev->next = u; // 원래 v 이전의 노드 다음에 u를 연결
        v->prev = u; // v 노드 전에 새로운 u 노드를 연결
    }
    void remove(DNode* v) {
    	DNode* u = v->prev; // v의 전 노드
        DNode* w = v->next; // v 다음 노드
        u->next = w; // u 다음에 w를 연결 (리스트에서 v의 연결을 끊음)
        w->prev = u; // w의 전에 u를 연결
        delete v; // v 노드 삭제
    }
};

 

환형 링크드 리스트(circularly linked list)

: 단일 링크드 리스트와 같은 노드를 갖는다. 하지면 heade와 tail을 갖는 대신 환형 링크드 리스트의 노드가 하나의 cycle로 연결되어 있다. 만약 next 포인터를 이용해서 어느 노드로부터 환형 링크드 리스트의 노드를 탐색하면 모든 노드를 방문하고 처음 시작했던 위치로 다시 돌아온다.

환형 링크드 리스트는 시작과 끝을 가지고 있지 않지만, 커서(cursor)라고 부르는 특별한 노드가 필요하다. 커서 노드는 환형 링크드 리스트를 탐색할 필요가 있을 때, 시작할 지점을 지정해준다.

커서에 의해 참조되는 원소를 back, 커서 다음의 원소를 front라고 부른다!!! 읭!?! 하겠지만 저 그림을 봤을 때 cusror에 의해 참조되는 노드(Back)와 이 노드 바로 다음 노드(Front) 사이에 있는 연결을 끊는다면 front 부분이 맨 앞, back 부분이 맨 뒤가 되는 단일 링크드 리스트가 될 것이다!!!

typedef string Elem; // 원소 타입

class CNode { // 환형 링크드 리스트 노드
private:
	Elem elem; // 노드의 원소 값
    CNode* next; // 다음 노드
    
    friend class CircleList; // CircleList가 CNode의 private 멤버에 접근하는 것을 허용
};

class CircleList { // 환형 링크드 리스트
public:
    CircleList() // 생성자
     : cursor(null) {}
    ~CircleList() { // 소멸자
    	while (!empty()) remove();
    }
    bool empty() const { // 비었는지
    	return cursor == NULL;
    }
    const Elem& front() const { // 커서 다음의 원소
    	return cursor->next->elem;
    }
    const Elem& back() const { // 커서의 원소
    	return cursor->elem;
    }
    void advance() { // 커서를 다음으로 이동
    	cursor = cursor->next;
    }
    void add(const Elem& e) { // 커서 뒤에 노드 추가
    	CNode* v = new CNode; // 새로운 노드 생성
        v->elem = e;
        if (cursor == NULL) { // 빈 리스트
        	v->next = v; // v는 자신과 연결
            cursor = v; 
        }
        else {
        	v->next = cursor->next;
            cursor->next = v;
        }
    }
    void remove() { // 커서의 다음 노드 삭제
    	CNode* old = new CNode; // 삭제할 노드
        old = cursor->next;
        if (old == cursor) { // old는 커서의 다음 노드인데 이게 커서와 같다는건 얘가 유일한 노드라는 뜻!
        	cursor = NULL;
        }
        else {
        	old->next = cursor->next; // 삭제할 노드의 연결 끊기
        }
        delete old; // 노드 삭제
    }
private:
	CNode* cursor; // 커서
};

---

참고 문헌

[1] Michael T. Goodrich, Roberto Tamassia, Davaid M. Mount, C++로 구현하는 자료구조와 알고리즘, WILEY, 2013.