이번에는 데이터 구조의 기초에 대해서 이야기해봅시다.
우리가 스택, 큐, 리스트, 집합 이러한 데이터 구조를 설계할 때 우선 기초적으로 쓰이는 재료가 있는데 그것이 바로
배열과 연결 리스트입니다.
배열을 여러분들이 c, python에서 배웠다시피 순차적인 기억 장소에 할당된 유한한 개수의 데이터 원소를 저장하는 방식입니다.
이러한 배열에는 1차원, 2차원, 3차원....... 등의 다차원 배열들이 있고 각 배열들은 행 우선 순서 즉, 저 차원 우선적으로 데이터 원소들이 메모리에 할당됩니다.
배열은 프로그래밍 언어를 공부하면서 꼭 거치게 되는 개념이니까 아시는 분들이 많을 거라고 생각합니다
하지만 연결 리스트는 처음 보는 분들이 더 많을 거라고 생각하는데요 원리를 알고 보면 크게 어렵지 않은 개념입니다:)
단순하게 설명하자면 위의 사진처럼, 데이터 원소를 가지는 박스들이 있고 그런 박스들이 연결되어 있는 것이 연결 리스트입니다.
연결 리스트의 정확한 의미 : 동적 메모리에 할당된, 링크에 의해 연결된 유한 개수의 데이터 원소 노드들!
노드란 아까 설명한 박스처럼 생긴 것이 노드인데요 정확하게 설명하자면 한 개의 데이터 원소를 저장하기 위해서-동적 메모리에 할당된 메모리입니다.
이러한 노드에 들어갈 수 있는 요소가 대표적으로 "원소"와 "링크"가 있습니다. 링크는 단어에서 눈치챌 수 있듯이, 다음의 노드를 가리키거나 이전의 노드를 가리킬 수 있습니다.
그러면 이제 여러 가지 연결 리스트의 종류와 특징들을 알아보겠습니다.
- 단일 연결 리스트 : 연속된 노드로 구성된, 가장 단순한 연결 데이터 구조입니다.
- 각 노드는 원소와 다음 노드의 주소를 저장하는 링크를 가집니다.
- 헤드 노드의 주소를 통해서 접근할 수 있습니다.
- 이중 연결 리스트 : 추가 링크를 사용해서 역방향 순회도 할 수 있습니다.
- 아까와 달리 이전 노드의 주소를 저장하는 링크도 추가적으로 가질 수 있습니다.
- 헤드 노드나 테일 노드의 주소를 통해서 접근할 수 있습니다.
- 원형 연결 리스트 : 마지막 노드의 링크가 헤드 노드의 주소를 가집니다.
- 헤더와 트레일러 : 헤드노드 앞에 특별한 헤더 노드를 추가해서 작업의 편의성을 증진할 수 있습니다
- 비슷하게 테일 노드도 트레일러 노드를 추가할 수 있습니다.
- 이러한 노드를 사용한다면 헤더 노드나 트레일러 노드를 통해서 연결 리스트에 접근할 수 있습니다.
여기까지 기초 데이터 구조에 대한 내용이었습니다!
