연결 리스트

연결 리스트는 데이터와 포인터를 가진 노드들이 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조.

vector와 같은 배열과 다르게 리스트의 중간 지점에서도 자료의 추가와 삭제가 빠르고,

메모리 선할당이 없고, 크기도 마음대로 정할 수 있을 뿐더러,

데이터의 추가/삭제시에도 이터레이터가 유효하다는 장점이 있지만,

랜덤 액세스가 느리다는 단점이 있다.

 

노드들이 포인터를 이용해서 연결되어 있는 방식에 따라 다음의 세 종류로 분류된다.

 

- 단일 연결 리스트 (Singly Linked List)

각 노드에 데이터와 하나의 포인터가 있고, 각 노드는 다음 노드를 가리키는 구조이다.

 

 

- 이중 연결 리스트 (Doubly Linked List)

각 노드에 데이터와 두 개의 포인터가 있고, 각 노드는 이전과 다음 노드를 가리키는 구조이다.

일반적으로 단일 연결 리스트보다 절반의 탐색 시간이 걸린다는 장점이 있지만,

노드 하나당 4바이트의 메모리(포인터)를 더 소모한다는 단점이 있다.

 

c++ STL의 list 라이브러리이다. (Doubly Linked List로 구현되어 있다)

위 코드는 배열로 리스트를 생성 및 초기화하고, 조작하는 코드이다.

 

 

- 원형 연결 리스트 (Circular Linked List)

단일 연결 리스트와 동일하지만, 맨 마지막 노드가 맨 처음 노드를 가리킨다는 차이점이 있는 구조이다.

원형 연결 리스트 사용시 무한 탐색이 가능하다.

// 활용 - 서버에서 로그 원형 순회 탐색
while(1) {
    for(log_list *cur = now; true; cur->next) {
        cur->print();
    }
}

// 원형이 아닐경우
while(1) {
    for(log_list *cur = head; cur != null; cur->next) {
        cur->print();
    }
}