연결 리스트의 개념
1. 리스트 (list)
주소록이나 친구들 이름을 나열할 때 처럼 나열한 목록을 리스트라고 칭한다.
리스트를 표현하는 방법은 아래와 같다.
리스트 명 = {자료 1, 자료 2, 자료 3, 자료 4, ..., 자료 n}리스트를 구현하는 방법은 일반적으로 순차 리스트와 연결 리스트 방법이 있다.
순차 리스트는 1차원 배열을 이용해 쉽게 구현이 가능하고, 자료들이 순서대로 저장되어 시작 위치와 원소의 크기를 알 경우 특정 원소의 위치를 알 수 있다는 장점이 있다. 하지만 자료의 삽입과 삭제가 일어날 경우 기존의 데이터를 전부 이동시키는 작업이 필요해 추가적인 작업과 시간을 요구한다.
따라서 일반적으로 연결 리스트를 많이 사용한다.
2. 연결 리스트 (Linked List)
앞에서 언급한 바와 같이 순차 리스트는 자료 이동이나 배열을 사용해 구현할 경우 메모리 사용의 비효율성이 발생할 수 있다.
이를 보완하기 위해 연결 리스트를 새용하며, 순차 리스트와의 가장 큰 차이점은 논리적인 순서만 유지한다는 점이다. 이는 논리적인 순서와 물리적인 순서가 일치한 순차 리스트와 대조적이다.
따라서 기억 장소 내에서 자료의 물리적 위치를 논리적 순서와 관계 없이 임의의 공간에 저장할 수 있다는 특징이 있다. 실생활의 예시로는 끝말잇기, 진주 목걸이 등을 생각할 수 있다.
연결 리스트의 기본 단위인 노드(Node)는 연결될 다음 자료에 대한 주소를 저장해야 하므로 자료와 링크의 구조로 되어있다.
위의 그림에서 알 수 있듯이 연결 리스트는 이런 기본 노드들이 서로 연결되어 필요할 때마다 노드를 만들어 자료를 저장한다. 연결 리스트의 마지막 노드에서는 null을 사용하는데 그 이유는 다음 노드를 가리킬 필요가 없기 때문이다.
그림으로 연결 리스트를 표현하면 아래와 같다.
연결 리스트의 종류
1. 단순 연결 리스트
노드가 하나의 링크 필드에 의해 다음 노드와 논리적으로 일렬로 연결된 구조를 단순 연결 리스트라고 한다.
2. 원형 연결 리스트
단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 해 리스트의 구조를 원형으로 만든 연결 리스트를 의미한다. 단순 연결 리스트와 유사하지만 마지막 노드가 첫 번째 자료를 가리킨다는 점이 다르다.
3. 이중 연결 리스트
단순 연결 리스트의 경우 링크가 한 방향으로 존재해 앞의 노드에 접근할 수 없다는 점이 있다. 이 문제를 해결하기 위해 나온 것이 이중 연결 리스트로서, 노드의 구조가 한 개의 자료와 두 개의 링크로 구성되어 앞 뒤로 연결할 수 있다는 점이 특징적이다.
참고
정관용, 임종범, 박병기, 복대원. (2013). 고등학교 정보과학 (pp. 203-206). 서울: (주)현대아트컴.
