연결 리스트

연결 리스트(linked list)란 추상적 자료형인 리스트를 구현한 자료구조로, 데이터 덩어리 (이하 “노드”)를 저장할 때 그 다음 순번의 자료가 있는 위치를 데이터에 포함하는 방식으로 자료를 저장한다.

노드 구조체에서 가장 중요한 부분은 struct NODE *next;이다. 얼핏 보면 구조체 자기 자신의 포인터를 멤버로 가지고 있는데, next 에는 NODE 구조체로 만든 다른 노드의 메모리 주소, 즉 자기 자신이 아닌 다른 노드의 메모리 주소를 저장한다.

struct NODE
{
  struct NODE *next;
  int data;
};

위의 NODE 구조체에서 데이터는 int형 하나만 저장했지만 실제로 사용할 때는 용도에 따라서 다양한 자료형으로 된 멤버 여러 개를 넣을 수 있다.

배열이 철수 1번, 영희 2번, 민수 3번, 순이 4번…식으로 자료의 순번을 맞춘다면, 연결리스트는 철수 다음 영희, 영희 다음 민수, 민수 다음 순이….식으로 자료를 연결해놓는다.배열에 비해 데이터의 추가/삽입 및 삭제가 용이하나 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없어 일반적으로 탐색 속도가 떨어진다. 즉 탐색 또는 정렬을 자주 하면 배열을, 추가/삭제가 많으면 연결 리스트를 사용하는 것이 유리하다.

단일 연결 리스트

다음 노드에 대한 참조만을 가진 가장 단순한 형태의 연결 리스트이다. 헤드 노드를 잃어버리면 데이터 전체를 못 쓰게 되며, 원소 탐색 복잡도가 얄짤없이 O(n) 이다.

이중 연결 리스트

다음 노드의 참조뿐만 아니라 이전 노드의 참조도 같이 가리키게 하면 이중 연결 리스트가 된다. 단순 연결 리스트에 비해 삽입이나 정렬의 작업량이 더 많고 자료구조의 크기가 더 커진다. 단일 연결 리스트에 비해 손상이 강하다.

원형 연결 리스트

단순 연결 리스트에서 마지막 원소가 널 대신 처음 원소를 가리키게 하면 원형 연결 리스트가 된다. 이와 비슷하게, 이중 연결 리스트의 처음과 끝을 서로 이으면 이중 원형 연결 리스트를 만들 수 있다.