리스트
리스트의 특징
- 리스트에서 항목들은 차례대로 저장된다.
- 리스트의 항목들은 순서 또는 위치를 가진다.
- 각 항목 간 순서의 개념이 없는 집합과는 다르다.
- 스택과 큐도 넓게 보면 리스트의 일종이다.
리스트의 기본 연산
- 삽입: 리스트에 새로운 항목을 추가
- 삭제: 리스트에서 항목을 삭제
- 탐색: 리스트에서 특정한 항목을 찾음
리스트의 구현
- 배열을 이용한 구현
- 연결리스트를 이용한 구현
배열을 이용한 리스트 구현
- 배열을 이용하여 순차적인 메모리 공간에 요소를 저장한다.
- 리스트의 순차적 표현이라고 한다.
배열로 구현된 리스트 특징
- 구현이 간단하다.
- 저장할 수 있는 요소의 개수가 고정된다.
- 리스트의 중간에 새로운 요소를 삽입/삭제하기 위해서는 기존 요소들의 위치를 이동해야 한다.
연결 리스트
- 리스트의 항목들을 노드(node)에 분산하여 저장
- 리스트의 크기를 동적으로 조정할 수 있음
- 요소의 삭제/삽입 연산에서 다른 요소들을 이동할 필요 없음
- 리스트의 연결된 표현이라고 함
연결 리스트로 구현된 리스트의 특징
- 삽입/삭제 연산 시 다른 요소들의 이동이 필요하지 않는다.
- 요소 저장을 위한 공간을 동적으로 조절할 수 있다.
- 배열에 비해 구현이 복잡하여 오류가 발생하기 쉽다.
연결 리스트의 구현
- 노드는 데이터필드와 링크필드로 구성된다.
- 데이터 필드 - 리스트의 요소를 저장한다.
- 링크 필드 - 다음 노드의 주소 값을 저장한다.
연결 리스트의 종류
- 단순 연결 리스트
- 원형 연결 리스트
- 이중 연결 리스트
단순 연결 리스트
- 노드마다 다음 노드의 주소를 저장하는 링크를 하나만 가진다.
- 마지막 노드의 링크 값은 NULL을 가진다.
원형 연결 리스트
마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트이다.
- 한 노드에서 다른 노드로의 접근이 가능하다.
- 한 노드에서 링크를 계속 따라 가면 모든 노드를 거쳐 자기 자신 노드로 돌아온다.
- 노드의 삽입과 삭제가 단순 연결 리스트보다 간단하다.
이중 연결 리스트
후속 노드 뿐만 아니라 선행 노드에 대한 위치 정보를 노드 마다 모두 저장하는 리스트이다.
- 후행 노드 뿐만 아니라 선행 노드도 쉽게 찾을 수 있다.
- 후행 노드 뿐만 아니라 선행 노드 위치 저장을 위한 링크 공간도 필요하다.
- 구현이 복잡하다.
