Linked Lists

특징: Linear Structure(선형구조)이며, before/after relation(전후 관계)을 갖는다.
장점: 크기 제한이 없다.
단점: 데이타에 빠르게 접근하는 것이 힘들 수 있다.

종류:

• Singly Linked List
• Doubly Linked List
• Circular Linked List

Node

Linke List는 일반적으로 연속적인 노드들의 집합이다.
각각의 노드는 기본적으로 다음 항목들을 포함한다.

element : 노드 상에 실제로 저장되는 데이터
next: link 또는 pointer라고 한다. 다음 노드의 주소를 가리킨다.

Singly Linked List의 마지막 노드의 next는 NULL이다.
Linked List에서의 맨앞 노드를 head, 맨 뒤 노드를 tail이라고 한다.

구현을 위한 설정

보통의 경우, 두 개의 클래스를 만들어 사용하게 된다.

1. Node 클래스

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

typedef string Elem;

class Node{
private:
    Elem element;
    Node* next;
    
    friend class LinkedList; 
};

2. Linked List 클래스

class LinkedList{
private:
    Node* head;
    Node* tail;
    
public:
    LinkedList(){
        head = nullptr;
        tail = nullptr;
    }
    ~LinkedList() {
        while (!empty()) {
            removeFront();
        }
    }
    bool empty() const; // Linked List 가 비었으면 true,아니면 false 반환 
    Elem front() const; // 맨앞노드(head)의 element 반환
    void addFront(const Elem& e); // head쪽에 새 노드 삽입 
    void removeFront(); //head 쪽의 노드 제거
    void addBack(const Elem& e); // tail쪽에 새 노드 삽입
    void removeBack();//tail 쪽의 노드 제거
    
};

기능 구현

1. empty

Linked List의 상태를 확인하고, 노드가 하나도 없어 비어있으면 true를, 비어있지 않으면 false를 리턴한다.

bool LinkedList::empty() const{
		return head == nullptr;
	}

원리: head가 nullptr이면 맨앞 노드가 없는 것이므로 비어있다는 뜻, true 리턴, head가 nullptr이 아니라면 false를 리턴할 것임.

2. front

head의 element 값을 확인한다.

Elem LinkedList::front() const {
		if (empty()) return -1; //예외 처리
    	return head->element;
	}

유의 포인트: Linked List가 비어있는 경우엔, head가 존재하질 않으므로 예외처리해준다.
원리: 그냥 head의 element 리턴.

3. addFront(e)

Linked List의 맨앞에 새로운 노드를 하나 삽입한다.

void LinkedList::addFront(const Elem& e) {
        Node* v = new Node;   
        if (tail == nullptr) {  
            tail = head;          
        }
        v->element = e;         
        v->next = head;  
        head = v;
    }

유의 포인트: Linked List가 비어있는 상태라면, 새로운 노드를 추가할 시에 노드가 하나만 생기는 것인데, 이러면 head랑 tail이랑 같아짐. head, tail모두 새 노드로 설정해줄 것.

원리:
1. 새 노드 할당
2. 새 노드의 element 초기화
3. 새 노드의 next를 head 노드로 설정
4. head 노드를 새 노드로 설정

4. removeFront

Linked List 맨 앞의 노드를 제거한다.

void LinkedList::removeFront() {
        if (empty()) return;    
        Node* old = head;     
        head = old->next;  
        delete old;  
        
        if (empty()) { 
            tail = nullptr;
        }
    }

유의 포인트: 다음의 경우들을 따져보아야한다.
1. 노드가 0개일 때(비었을 때)
2. 노드가 1개일 때
3. 그 외

원리:
1. 기존의 head 노드를 old라는 노드 포인터로 가리키기
2. old의 next 노드를 head 노드로 설정
3. old 노드 제거

5. addBack(e)

Linked List의 맨뒤에 새로운 노드를 하나 삽입한다.

void LinkedList::addBack(const Elem& e) {
        Node* v = new Node;       
        v->element = e;          
        v->next = nullptr;       
        
        if (empty()) {        
            head = tail = v;    
        } else {
            tail->next = v;    
            tail = v;       
        }
    }

유의 포인트: 다음의 경우들을 따져보아야한다.
1. 노드가 0개일 때(비었을 때)
2. 그 외

원리:
1. 새 노드 할당
2. 새 노드의 element를 초기화
3. 새 노드의 next가 NULL을 가리키도록 설정
4. tail의 next를 새 노드로 설정
5. 새 노드를 tail노드로 지정

6. removeBack

Linked List 맨 뒤의 노드를 제거한다.

void LinkedList::removeBack() {
        if (empty()) return;
        Node* current = head;
        if (current == tail) { 
        	head = tail = nullptr;
            delete current;
        }
        
        else{
        	while (current->next != tail) {
            current = current->next;
        	}
        }
        tail = current;
        delete tail->next;        
        tail->next = nullptr;
    }

유의 포인트: 다음의 경우들을 따져보아야한다.
1. 노드가 0개일 때(비었을 때)
2. 노드가 1개일 때
3. 그 외

원리:
1. head에서부터 시작하여 tail직전의 노드 탐색
2. tail 직전의 노드를 tail노드로 설정
3. 이 새로운 tail노드의 next(기존의 tail)을 삭제
4. 이 새로운 tail노드의 next를 NULL로 설정

덤: print

Linked List의 모든 노드들의 element 순서대로 출력

void print() const {
        Node* current = head;
        while (current != nullptr) {
            cout << current->element << " -> ";
            current = current->next;
        }
        cout << "nullptr" << endl;
    }

수고