정의
- 배열 구조의 문제점인 삽입과 삭제의 어려움을 해결하기 위해 고안한 자료구조로, 삽입과 삭제 빈번한 작업과 적합하다.
- 노드(Node)를 크게 데이터 필드와 링크 필드로 나누어 다음 노드가 기억된 공간의 주소를 이전 노드의 링크 필드에 기억시키는 방식으로 모든 노드들을 하나의 리스트로 연결한다.
- 논리적 데이터 순서와 물리적 데이터 순서가 동일하지 않으므로 후속 데이터 액세스를 위해서는 포인터가 필요하다. 즉, 노드들은 논리적으로는 순차적으로, 물리적으로는 비순차적으로 저장된다.
단순 연결 리스트
- 임의의 문자를 접근하기 위해서는 처음부터 순차 탐색을 해야만 한다. 그러므로 임의의 원소의 값을 수정하는 연산이 일어날 경우 탐색 시간이 많이 필요하다.
원형 연결 리스트
- 단순 연결 리스트의 마지막 노드가 null link를 갖는 대신에 리스트에서 처음 노드의 포인터를 갖도록 구성한 리스트이다.
- 임의의 노드 검색 시 처음 노드부터 찾지 않고 현재 노드부터 검색할 수 있다.
이중 연결 리스트
- 어떤 노드에 대해 다음 노드뿐만 아니라 전 노드까지 알 수 있도록 하여 한 가지 방향이 아닌 양쪽 방향의 탐색이 가능하게 구성한 것이다.
- 원형 리스트가 리스트를 뒤로 순회할 수 없다는 점과 삭제하고자 하는 노드에 대한 포인터만으로는 그 노드를 삭제할 수 없다는 단점을 보완했다.
- 각 노드에 좌, 우측 2개의 포인터가 있으며, 각 포인터는 각각 좌우 노드를 가리키는 구조이다.
- 운영체제의 동적 메모리 관리에 가장 적합하다.
