배열 리스트
임의의 리스트 객체에는 아래의 그림과 같이 2개의 필드, 원소들이 저장되는 배열 필드와 원소의 총 수를 저장하는 필드가 있다. 또한, 이를 지원하는 핵심적인 10가지의 작업들이 있다.(ADT 리스트)
그리고 각 필드와 작업의 의미는 아래 그림과 같다.
-
배열 리스트의 구현(제네릭 버전)
배열 리스트를 구현할때 일반적인 방법보다 제네릭 형태로 작성하면 범용성도 보장되고 타입체크 기능도 갖출 수 있다. 따라서 인터페이스 함수처럼 파라미터를 주는 베네릭 방법을 권한다. 위 내용에 따라 배열리스트를 구현하면 다음 그림들과 같다.
(리스트 인터페이스)
이것 외의 작업들 또한 같은 형식으로 구현해 나가면 된다.연결 리스트
-
연결 리스트의 객체 구조
연결 리스트는 배열의 공간 낭비를 피할 수 있는 자료구조이다. 원소가 추가될 때마다 공간을 할당받아 추가하는 동적 할당 방식을 따르기 때문이다.
연결 리스트의 노드는 원소를 저장하는 필드와 다음 노드를 가리키는 필드 next로 구성된다.
연결 리스트의 객체는 리스트의 노드를 직접 저장할 필요가 없고 리스트의 첫 번째 노드에 접근할 수 있는 래퍼런스만 갖고 있으면 된다.
- 연결 리스트의 구현
배열 리스트와 연결 리스트의 비교
배열 리스트는 공간적인 측면에서 정적이고 연결 리스트는 반대로 동적이라고 할 수 있다.
그리고 검색에 있어서 배열 리스트와 연결 리스트는 시간 복잡도에 있어서 다른 측면을 나타낸다.
- 배열 리스트 (Array List)
접근 (Access)
시간 복잡도: O(1)
설명: 인덱스를 통해 임의의 요소에 즉시 접근할 수 있다.
탐색 (Search)
시간 복잡도: O(n), 정렬된 경우 O(nlogn)
설명: 원하는 요소를 찾기 위해 배열을 처음부터 끝까지 탐색해야 한다.
- 연결 리스트 (Linked List)
접근 (Access)
시간 복잡도: O(n)
설명: 연결 리스트는 인덱스를 통한 직접 접근이 불가능하며, 원하는 요소에 접근하기 위해서는 첫 번째 노드부터 순차적으로 탐색해야 한다.
탐색 (Search)
시간 복잡도: O(n)
설명: 원하는 요소를 찾기 위해 리스트를 처음부터 끝까지 탐색해야 한다.
