[자료구조] 연결 자료구조 (Linked List)

개념

연결리스트는 기억 공간의 노드들을 연속적이지 않게 빈 공간에 저장한다. 노드들끼리 연결하기 위해서 데이터 필드 외에 링크 필드가 하나씩 더 필요하다.

특징

1. 노드의 삽입, 삭제가 간편하다.
2. 연속적인 저장 공간이 없어도 저장이 가능하다.
3. 링크 필드를 사용하므로 기억 공간이 많이 필요하다.
4. 특정 노드 검색 시 무한 루프에 빠질 수 있다.

단순 연결 리스트

단순 연결 리스트(singly linked list)는 1개의 노드에 1개의 데이터 필드와 1개의 포인터(연결 주소 값)를 갖는다. 자료의 검색은 한쪽 방향으로만 진행된다. 처음 노드의 주소 값은 head에 있고, 마지막 노드의 주소 값은 NULL로 표현한다.

원형 연결 리스트

원형 연결 리스트(circular linked list)는 마지막 노드의 링크가 맨 처음 노드의 주소를 갖는다. 따라서 연결 리스트의 처음과 끝이 없는 구조이다. 원형 연결 리스트는 결합, 분리 작업이 효율적이고 처음과 끝의 구별이 없어 한 개의 노드에서 다른 노드로의 탐색 알고리즘이 단순해진다. 그러나 노드를 찾을 때 무한 루프에 빠질 수 있어 데이터를 가지고 있지 않은 헤더 노드를 사용하는 경우가 있다.

이중 연결 리스트

이중 연결 리스트(doubly linked list)는 1개의 노드에 1개의 데이터 필드와 좌측과 우측, 2개의 포인터(연결 주소 값)를 갖는다. 좌측 포인터는 이전 노드의 주소, 우측 포인터는 다음 노드의 주소를 저장한다. 따라서 양방향의 자료 검색이 가능하다. 제일 처음 노드의 주소 값은 head에 있고, 마지막 노드의 우측 주소 값은 NULL로 표현한다.

추상 데이터 타입(ADT)

• front(): 리스트의 첫 번째 원소를 반환한다.
• back(): 리스트의 마지막 원소를 반환한다.
• push_front(val): 리스트의 맨 앞에 val을 삽입한다.
• push_back(val): 리스트의 맨 뒤에 val을 삽입한다.
• pop_front(): 리스트의 첫 번째 원소를 삭제한다.
• pop_back(): 리스트의 마지막 원소를 삭제한다.

구현

C++에서 struct를 이용하여 구현할 수 있다.