리스트
- 리스트란 데이터를 순서대로 나열한 자료구조이다.
선형 리스트
- 데이터를 순서대로 나열해 놓은 리스트를 선형 리스트 또는 연결 리스트라고 한다.
- 리스트의 데이터는 노드 또는 요소라고 부르며, 각각의 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있다.
- 처음과 끝에 있는 노드를 각각 머리 노드, 꼬리 노드라고 부른다.
구현 방법
- 요소를 추가할 때 마다 객체를 생성하고 요소를 삭제할 때마다 객체를 제거하는 방법 : 메모리 영역을 만들고 해제하는데 필요한 비용을 무시할 수 없음.
- 배열에 객체를 미리 담아놓고 사용하는 방법 : 데이터의 수가 크게 바뀌지 않고 데이터 수의 최댓값을 미리 알야아한다. 대신, 효율적이다.
원형 리스트
- 연결 리스트의 꼬리 노드가 머리 노드를 가리키면 원형 리스트라고 부른다.
- 고리모양으로 나열된 데이터를 저장할 때 알맞는 자료구조이다.
이중 연결 리스트
- 연결 리스트의 큰 단점은 다음 노드는 찾기 쉽지만 앞쪽의 노드는 찾을 수 없다.
- 노드를 앞뒤로 연결해서 그 단점을 개선한 자료구조이다ㅏ.
원형 이중 연결 리스트
- 원형 리스트와 이중 연결 리스트를 합친 것이다.
do for me