Array(배열)
정의
- 같은 타입의 변수들로 이루어진 유한 집합
- 논리적인 순서와 물리적인 순서가 같은 구조
-
Element(요소)
배열을 구성하는 각각의 값 -
Index(인덱스)
배열에서의 위치를 가리키는 숫자
값에 대한 유일무이한 식별자 (랜덤 엑세스 가능)
특징
-
크기가 정해져 있다.
요소 삭제 시 해당 공간이 그대로 남아 있음. → 메모리의 낭비 -
조회 속도가 빠르다.
인덱스를 활용하여 빠르게 조회 가능
메모리에 연속적으로 데이터가 저장되기 때문
(Array)List(순차 리스트)
정의
- 데이터들을 순서대로 메모리에 연속하여 저장하는 자료 구조
- 논리적인 순서와 물리적인 순서가 같은 구조
-
Element(요소)
배열을 구성하는 각각의 값 -
Index(인덱스)
배열에서의 위치를 가리키는 숫자
값에 대한 유일무이한 식별자 (랜덤 엑세스 가능)
특징
-
크기가 정해져 있지 않다.
중간에 데이터를 추가/삭제 시 메모리 공간이 확장/축소 된다.
Array의 문제점 해결 -
조회 속도가 빠르다.
인덱스를 활용하여 빠르게 조회 가능 -
중간에 데이터 추가/삭제 시 시간이 오래 걸린다.
자료의 이동이 생기기 때문에 오버헤드(연산 추가 및 메모리 낭비)가 발생한다.
LinkedList(연결 리스트)
정의
- 순서가 있는 데이터들의 모임 (각 노드에 다음 노드의 주소가 저장 됨)
- 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재 라는 장점을 취한 자료 구조
-
Element(요소)
리스트를 구성하는 각각의 값 -
Index(인덱스)
몇 번째 데이터인가 정도(순서)의 의미를 가짐
유일무이한 식별자가 아님
특징
-
크기가 가변적이다.
빈 요소는 허용하지 않는다. -
조회 속도가 느리다.
인덱스가 순서의 의미만 갖기 때문에, 요소의 위치를 바로 알 수 없다. -
중간에 데이터 추가/삭제 시 빠르다.
주소에 의해 연결 되기 때문에 추가/삭제가 용이 함
기능
- 처음, 끝, 중간에 엘리먼트를 추가/삭제 하는 기능
- 리스트에 데이터가 있는지를 체크하는 기능
- 리스트의 모든 데이터에 접근할 수 있는 기능
단일 연결 리스트
- 하나의 노드는 데이터 필드와 링크 필드로 구성 된다.
- 데이터 필드 : 데이터 저장- 링크 필드 : 다음 노드의 주소 저장
- 마지막 노드의 링크 필드는 Null 이다.
원형 연결 리스트
- tail(마지막 노드)의 링크 필드라 head(맨 앞의 노드) 이어야 한다.
- 맨 앞에 노드를 삽입할 경우 : tail의 링크 필드를 수정 해 주어야 한다.
이중 연결 리스트
- 단일 연결 리스트나 원형 연결 리스트는 현재 노드의 이전 노드를 접근하기 위해서는 리스트를 한번 순회 하여야 한다.
- 이점을 보완하여, 이전 노드의 주소를 저장한 것이 이중 연결 리스트 이다.
- 링크 필드를 두 개 가지고 있다.
- Left Link Field : 이전 노드의 주소 저장
- Right Link Field : 다음 노드의 주소 저장
Array나 ArrayList는 index를 갖고 있기 때문에 검색이 빠르다.
LinkedList는 처음부터 살펴 보아야 하므로(순차) 검색에 있어서는 시간이 더 오래 걸린다.
