✍️ 리스트(List)
리스트의 ADT는 다음과 같다.
리스트는 삽입과 삭제를 다양한 곳에서 할 수 있다.
🔍 배열로 구현된 리스트
장점? 구현이 간단하고 속도가 빠름
단점? 리스트의 크기가 고정, 리스트 중간에 데이터의 삽입과 삭제 시 기존 데이터의 이동이 발생
삽입이나 삭제의 시간복잡도는 최악의 경우 O(n). why? 모든 항목을 이동하는데 시간이 필요하기 때문
🔍 연결 리스트
장점? 크기 제한이 없음, 중간에 삽입과 삭제가 용이
단점? 구현복잡, 임의의 항목 추출 시 배열보다 오래 걸림
리스트의 항목들을 노드(node)라고 하는 곳에 분산하여 저장하는데 노드는 데이터 필드와 링크 필드를 가지고 있다.
헤드 포인터? 연결리스트의 첫 번째 노드를 가리키고 있는 변수
NULL? 더 이상 연결 노드가 없다는 의미 즉, 다음 주소를 갖고 있지 않는다.
연결 리스트의 종류는
- 단순 연결 리스트
- 원형 연결 리스트
- 이중 연결 리스트
로 구성되어 있다.
✍️ 단순 연결 리스트
말 그대로 단순하게, 하나의 링크 필드를 이용하여 연결한다. 마지막 노드의 링크 값은 당연하게도 NULL이다.
✍️ 원형 연결 리스트
원형 연결 리스트란? 마지막 노드의 링크가 첫 번째 노트를 가리키는 리스트
헤드 포인터를 연결리스트의 첫 번째 노드를 가리키는 것이 아니라 마지막 노드를 가리키게 하여 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 용이
✍️ 이중 연결 리스트
이중 연결 리스트란? 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트
선행 노드가 없는 단순 연결 리스트의 문제점을 해결하였지만 공간을 많이 차지하고 코드가 복잡하다는 단점이 있다.
헤드 노드? 데이터를 가지지 않고 단지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드. 반드시 필요한 게 아니라서 포인터로 만들어도 된다.
- 헤드 포인터와의 구별 필요
- 공백상태에서는 헤드 노드만 존재
