연결리스트란?
- 데이터가 순서대로 나열되고 각 데이터가 연결되어있는 구조, 자료의 논리적인 순서와 물리적인 순서 불일치
- 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식
- 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않음
- 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현해 크기 변경이 유연하고 효율적으로 메모리를 사용
- 삽입과 삭제가 효율적이지만 구현이 복잡하다
- 크기가 제한되지 않으며 하나의 링크 필드를 이용하여 연결하고 후속 노드를 찾기 쉽다
- 마지막 노드의 링크 값은 NULL이다
- 자료를 노드에 담아 보관하며 필요할 때 마다 노드를 생성
- 시작노드는 헤드포인터뿐이다.
- 연결리스트에서 각각의 원소를 노드(NODE)라고 하며 노드가 갖고 있는 것은 데이터와 뒤쪽 노드를 가리키는(참조하는) 포인터이다. 즉, 노드는 <항목, 주소> 쌍이다.
- 데이터 필드는 리스트의 원소, 즉 데이터 값을 저장하는 곳
- 링크 필드는 다른 노드의 주소 값을 저장하는 장소(포인터)
- 위와 같은 포인터를 이용한 연결리스트는 노드를 삽입, 삭제 할 때 데이터를 이동하지 않고 처리하는 특성이 있다.
- 노드를 삽입, 삭제할 때 마다 내부에서 노드용 인스턴스를 생성하고 소멸시키고 이 때 메모리를 확보하고 해제하는데 쓰는 비용이 발생하는데 이는 커서를 이용한 연결리스트를 통해 이를 해결할 수 있다.
- 뒤쪽 포인터는 뒤쪽 노드가 저장되는 원소의 인덱스이며 인덱스로 나타낸 포인터를 커서라 칭함
- 위 그림을 보면 배열에 각각의 원소에는 노드가 저장 되고 다음 노드의 인덱스를 저장하는 커서가 존재하는데 꼬리 노드의 커서는 -1이며 머리 노드를 나타내는 head에 저장된 값도 커서이기에 인덱스 1번에 있는 것이 머리 노드가 된다.
- 이를 이용하면 커서만 바꿔서 원소를 삽입, 삭제가 가능해 원소의 이동이 필요하지 않다.
- 커서를 이용한 연결 리스트의 단점은 노드를 삭제하고 추가 시에 빈 공간들을 활용하지 못한다는 것
프리 리스트란?
- 삭제된 레코드 그룹을 관리할 때 사용하는 자료구조
- 앞에서 발생한 삭제 후 비어 있는 배열의 문제를 해결 가능
- 기존에는 삭제되어 비어 있는 부분을 알 수 없어 단순히 마지막으로 채워진 노드 다음 인덱스에 새로운 노드를 삽입했지만 프리 리스트를 사용하면 노드를 삭제 시에 해당 노드가 존재했었던 배열의 인덱스를 저장해 새로운 노드를 삽입 시에 프리 리스트에 저장된 값이 있다면 해당 값에 해당하는 인덱스에 노드를 삽입하여 삭제 후에 비어 있는 배열 공간을 없앨 수 있다.
원형 리스트 : 꼬리노드의 뒤쪽 포인터가 None이 아니라 머리 노드의 포인터 값이 되어 고리 모양으로 늘어선 형태
이중 연결 리스트 : 연결 리스트의 가장 큰 단점인 뒤쪽 노드를 찾기 쉬운 반면 앞쪽 노드는 찾기가 어렵다는 점을 개선한 리스트로 각 노드에스는 뒤쪽 노드에 대한 포인터뿐만 아니라 앞쪽 노드에 대한 포인터가 주어짐
원형 이중 연결 리스트 : 원형 리스트와 이중 연결 리스트를 결합한 형태
사진 출처:
쉽게 배우는 C 자료구조 | 생능출판사
코딩을 조금이라도 해 보았다면 프로그래밍이 자료(data)를 주로 다루는 것임을 알 수 있을 것이다. 우리가 프로그램을 개발할 때 가장 먼저 해야 할 일은 처리할 자료를 컴퓨터가 잘 다룰 수 있
www.booksr.co.kr
