[자료구조와 알고리즘] 3장 연결 리스트

 

1장 연결 리스트

 

1. 리스트

 가. 리스트(list)란?

• 순서를 가진 데이터의 모임. 목록
• (e.g.) TO DO 리스트, 요일 (일요일, 월요일... , 토요일) etc

 나. 리스트의 주요 연산

• 원소의 참조, 삽입 (insert), 삭제(remove), 검색 (search), etc

 다. 대표적인 리스트 구현 방법

 

2. 연결 리스트

가. 연결 리스트 (linked list)란?

• 데이터와 링크로 구성된 노드(node)가 연결되어 있는 자료 구조
  • 데이터 (data): 정수, 문자열, 복합 자료형 등 (실제 저장할 값)
  • 링크 (link, next): 다음 노드 (다른 노드)를 가리키는 포인터
  • 노드 (node): 데이터와 링크로 이루어진 연결 리스트 구성 단위 (연결리스트를 구성하는 가장 작은 구성 단위)

 
 나. 연결 리스트 클래스

struct Node
{
	int data;
    Node* next;
};
 
class LinkedList
{
private:
 	Node* head;
public:
	LinkedList() : head(NULL) {} // 생성자
    ~LinkedList();				// 소멸자
    
    void push_front(int val); // 추가
    void pop_front(); //기존 데이터 삭제
    
    void print_all(); // 현재 LinkedList 안에 있는 모든 데이터를 화면에 출력
    bool empty(); // 안에 노드가 하나라도 있는지 없는지 판단해서 T/F로 반환

 
 다. 연결 리스트 맨 앞에 노드 삽입하기

 라. 연결 리스트 맨 앞 노드 삭제하기

 마. 연결 리스트 전체 데이터 출력하기

 
 바. 연결 리스트가 비어 있는지 확인

bool empty() const
{
	return head == NULL;
}

 
 사. 연결 리스트 제거

~LinkedList()
{
	while (!empty()) {
    	pop_front();
    }
}

 

 
3. 연결 리스트의 장단점

 가. 연결 리스트의 장점

• 임의의 위치에 원소의 삽입 & 삭제가 효율적: O(1)
• 크기 제한이 없음

 나. 연결 리스트의 단점

• 임의의 원소 접근이 비효율적: O(N)
• 링크를 위한 여분의 공간 사용
• 구현이 복잡

 

2장 이중 연결 리스트

1. 연결 리스트 종류

 가. 단순 연결 리스트 (singly linked list)

• 다음 노드에 대한 링크만 가지고 있는 연결 리스트 
• 한쪽 방향으로만 순회(traverse)가 가능 (단방향 연결 리스트)

 나. 이중 연결 리스트 (doubly linked list)

• 이전 노드와 다음 노드에 대한 링크를 가지고 있는 연결 리스트
• 양방향 순회가 가능 (양방향 연결 리스트)

 다. 원형 연결 리스트 (circular linked list)

• 일반적인 연결 리스트의 마지막 노드 링크가 처음 노드를 가리키도록 구성된 자료 구조
• 처음 노드가 다시 나타나면 순회를 멈춤

2. 이중 연결 리스트

가. 이중 연결 리스트의 구조

struct Node
{
	int data;
    Node* prev; // 이전 노드
    Node* next; // 다음 노드
};

struct Node
{
	int data;
    Node* prev;
    Node* next;
}

class DoublyLinkedList
{
private:
	int count;
    Node* header;
    Node* trailer;
public:
	DoublyLinkedList(); // 생성자
    ~DoublyLinkedList(); // 소멸자
    
    void insert(Node* p, int val); // p가 가리키고 있는 노드 앞에 새로운 값 val을 추가
    void erase(Node* p);
    
    void print_all();  // 모든 데이터 순방향 출력
    void print_reverse(); // 모든 데이터 역방향 출력
    
    void push_front(int val); // 연결리스트 맨 앞에 값을 추가
    void push_back(int val); // 맨 뒤에 값 추가
    
    void pop_front(); // 맨 앞에 있는 값 제거
    void pop_back(); // 맨 뒤에 값 제거
};

 
 
 나. 이중 연결 리스트 생성

DoublyLinkedList()
{
	count = 0;
    header = new Node {0, NULL, NULL};
    trailer = new Noder {0, NULL, NULL};
    header->next = trailer;
    trailer->prev = header;
}

 
 다. 이중 연결 리스트에 원소 삽입
 

void insert(Node* p, int val)
{
	Node* new_node = new Node {val, p->prev, p};
    new_node->prev->next = new_node;
    new_node->next->prev = new_node;
    count++;
}

void push_front(int val)
{
	insert(header->next, val);
}

void push_back(int val)
{
	insert(trailer, val);
}

 
 라. 이중 연결 리스트에서 노드 삭제하기

void erase(Node* p)
{
	p->prev->next = p->next;
    p->next->prev = p->prev;
    count--;
}

void pop_front()
{
	if (!empty())
    	erase(header->next);
}

void pop_back()
{
	if (!empty())
    	erase(trailer->prev);
}

 
 마. 이중 연결 리스트 전체 데이터 출력하기

void print_all()
{
	Node* curr = header->next;
    
    while (curr != trailer) 
    	std::cout << curr->data << ", ";
        curr = curr->next;
    }
  	std:::cout << std::endl;
}

 
 바. 이중 연결 리스트 전체 데이터를 역순으로 출력하기

~DoublyLinkedList()
{
	while (!empty()) {
		pop_front();
    }
    delete header;
    delete trailer;
}

 
 사. 기타 멤버 함수

bool empty() const
{
	return count == 0;
}
int size() const
{
	return count;
}

 
 아. 이중 연결 리스트 제거

~DoublyLinkedList()
{
	while (!empty()) {
    	pop_front();
    }
 	delete header;
    delete trailder;
}

 

3. 이중 연결 리스트의 장단점

가. (단순 연결 리스트 대비) 이중 연결 리스트의 장점

• 링크가 양방향이므로 양방향 검색이 가능

 나. (단순 연결 리스트 대비) 이중 연결 리스트의 단점

• 이전 노드 링크를 위한 여분의 공간 사용
• 데이터의 삽입과 삭제 구현이 더 복잡

 

3장 향상된 이중 연결 리스트 클래스

 

1. 향상된 이중 연결 리스트 클래스

가. DoublyLinkedList 클래스에 추가할 기능

• 반복자(iterator) 지원
• 데이터 검색 가능
• 범용 데이터 저장을 위한 클래스 템플릿 작성

 

2. 반복자 지원

 가. 반복자 클래스를 중첩 클래스 형태로 정의

#include <iostream>

using namespace std;

class iterator
{
private:
    Node* ptr;
public:
    iterator() : ptr(NULL) {}
    iterator(Node* p) : ptr(p) {}

    T& operator() {return ptr->data;}
    
    interator& operator++() // ++it
    {
        ptr = ptr->next;
        return *this; // 자기 자신을 참조 형태로 반환
    }

    iterator& operator--()
    {
        ptr = ptr->prev;
        return *this;
    }

    bool operator == (const iterator& it)
    {
        return ptr == it.ptr;
    }
    bool operator != (const iterator& it)
    {
        return ptr != it.ptr;
    }
    
    friend class DoublyLinkedList;
};

 
 나. DoublyLinkedList 클래스에 begin()과 end() 멤버 함수 추가

iterator begin() const
{
	return iterator(header->next);
}
iterator end() const
{
	return iterator(trailer);
}

 
 다. DoublyLinkedList 클래스에서 insert(), push_front(), push_back() 함수 수정

void insert(const iterator& pos, const int val)
{
	Node* curr = pos.ptr;
    Node* new_node = new Node {val, curr->prev, curr};
    new_node->prev->next = new_node;
    new_node->next->prev = new_node;
    count++;
}

void push_front(const T& data)
{
	insert(begin(), data)
}
void push_back(const T& data)
{
	insert(end(), data);
}
void erase(const iterator& pos)
{
	Node<T>* curr = pos.ptr;
    curr->prev->next = curr->next;
    curr->next->prev = curr->prev;
    delete curr;
    count--;
}

void pop_front()
{
	if (!empty()) 	erase(begin());
}
void pop_back()
{
	if (!empty()) erase(--end()):
}

 
 라. DoublyLinkedList 클래스에 find() 멤버 함수 추가

iterator find(const int val)
{
	Node* curr = header->next;
    
    while (curr->data != val && curr != trailer)
    	curr = curr->next;
        
    return iterator(curr);
}

 

3. 범용 데이터 저장을 위한 클래스 템플릿 작성

 가. DoublyLinedList 클래스를 클래스 템플릿으로 변환하기

• Node DoublyLinkedList 클래스를 모두 typename T를 사용하는 클래스 템플릿으로 변경
• Node DoublyLinkedList 클래스에서 데이터를 표현하는 int를 T로 바꾸고, Node를 Node<T>로 변경

template <typename T>
struct Node
{
	T data;
    Node* prev;
    Node* next;
};

template <typename T>
class DoublyLinkedList
{
private:
	int count;
    Node<T>* header;
    Node<T>* trailer;
};

 
 

4강 std::list와 std::forward_list

 

1. std::list와 std::forward_list

 가. std::list

• 이중 연결 리스트를 구현한 컨테이너

template <class T, class Allocator = std::allcator<T>>
class list;

• 어느 위치라도 원소의 삽입 또는 삭제를 상수 시간으로 처리: O(1)
• 그러나 특정 위치에 곧바로 접근할 수 없음
  • std::vector처럼 [] 연산자를 이용한 랜덤 액세스는 지원 안 함
  • begin(), end() 등의 함수로 얻은 (양방향) 반복자와 ++, -- 연산자로 위치 이동
• <list>에 정의되어 있음

 나. std::list 주요 연산

#include <iostream>
#include <list>

using namespace std;

int main()
{
	list<int> l1;
    l1.push_back(10); // 10
    l1.push_back(20); // 10, 20
    
    list<int> l2{10, 20, 30, 40};
    
    l2.splice(l2.end(), l1); // 10, 20, 30, 40, 10, 20
    
    l2.sort(); // 10, 10, 20, 20, 30, 40
    
    l2.unique(); // 10, 20, 30, 40

 다. std::forward_list

• 단순 연결 리스트를 구현한 컨테이너 

template <class T, class Allocator = std::allocator<T>>
class forward_list;

• begin() 함수로 (순방향) 반복자를 얻을 수 있고, 오직 ++ 연산만 사용 가능
• std::list 보다 빠르게 동작하고, 적은 메모리를 사용
• C++11부터 지원
• <forward_list>에 정의되어 있음

#include <iostream>
#include <forward_list>

using namespace std;

int main()
{
	forward_list<int> l1 {10, 20, 30, 40};
    l1.push_front(40); // 40, 10, 20, 30, 40
    l1.push_front(30); // 30, 40, 10, 20, 30, 40
    
    int cnt = distance(l1.begin(), l1.end()); // 6
    
    l1.remove(40); //30, 10, 20, 30
    l1.remove_if([] (int n) { return n > 20; }); // 10, 20
    
    for (auto a: l1)
    	cout << a << ", ";
    cout << endl;