[자료구조] 배열과 리스트의 차이점(Array vs List) 및 정리

Array(배열) vs List(리스트), Array(배열), Sequential List(순차 리스트), ArrayList(배열 리스트), LinkedList(연결 리스트), 단일 연결 리스트, 원형 연결 리스트, 이중 연결 리스트

 

Array(배열) vs List(리스트)

 - Array는 메모리 상에 데이터가 연속적으로 저장되고 List는 메모리 상에 데이터가 비연속적으로 저장된다는 차이점은 일반적으로 Array와 연결 리스트(LinkedList)의 차이점이다.

 - Array와 순차 리스트(Sequential List), 배열 리스트(ArrayList)는 자료구조 크기에 대한 지정유무 차이가 있다.

 - Array나 ArrayList는 index를 갖고 있기 때문에 검색이 빠르지만 LinkedList는 처음부터 살펴 보아야 하므로(순차) 검색에 있어서는 시간이 더 오래 걸린다.

 - 반대로 수정이나 삭제를 함에 있어서는 LinkedList가 Array와 ArrayList보다 속도가 빠르다.

 - List의 두 가지 종류
  * 순차 리스트(Sequential List), 배열 리스트(ArrayList): 자료들을 순차적인 메모리공간안에 연속하여 저장되는 자료구조이다.
  * 연결 리스트(Linked List): 자료를 저장하기위해 자료 부분(데이터 필드)과 위치를 알려주는 노드 부분(링크 필드)으로 구성한 자료구조이다.

 

 

Array(배열)

1. 같은 타입의 변수들로 이루어진 유한 집합이다.
2. 논리적인 순서와 물리적인 순서가 같은 구조이다.

Element(요소) => 배열을 구성하는 각각의 값이다.
Index(인덱스) => 배열에서의 위치를 가리키는 숫자로 요소에 대한 유일무이한 식별자이다.

특징

1. 크기가 정해져 있다.
2. 요소 삭제 시 해당 공간이 그대로 남아 있고 이는 메모리의 낭비로 이어진다.
3. 조회 속도가 빠르다.
4. 인덱스를 활용하여 빠르게 조회가 가능하다.
5. 메모리에 연속적으로 데이터가 저장된다.

 

 

Sequential List(순차 리스트), ArrayList(배열 리스트)

1. 데이터들을 순서대로 메모리에 연속하여 저장하는 자료 구조이다.
2. 논리적인 순서와 물리적인 순서가 같은 구조이다.

Element(요소) => 배열을 구성하는 각각의 값이다.
Index(인덱스) => 배열에서의 위치를 가리키는 숫자로 요소에 대한 유일무이한 식별자이다.

특징

1. 크기가 정해져 있지 않다.
2. 중간에 데이터를 추가 및 삭제 시 메모리 공간이 확장 및 축소된다.
3. Array의 문제점을 해결했다.
4. 조회 속도가 빠르다.
5. 인덱스를 활용하여 빠르게 조회가 가능하다.
6. 중간에 데이터 추가/삭제 시 시간이 오래 걸린다.
7. 자료의 이동이 생기기 때문에 오버헤드(연산 추가 및 메모리 낭비)가 발생한다.

 

LinkedList(연결 리스트)

1. 순서가 있는 데이터들의 모임이다. (각 노드에 다음 노드의 주소가 저장된다)
2. 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 낭비없는 데이터의 적재 라는 장점을 취한 자료 구조이다.

Element(요소) => 리스트를 구성하는 각각의 값이다.

Index(인덱스) => 순서의 의미를 가질뿐 유일무이한 식별자가 아니다.

 

특징

1. 크기가 가변적이다.
2. 빈 요소는 허용하지 않는다.
3. 조회 속도가 느리다.
4. 인덱스가 순서의 의미만 갖기 때문에, 요소의 위치를 바로 알 수 없다.
5. 리스트 중간에 데이터 추가 및 삭제 시 빠르다.
6. 주소에 의해 연결 되기 때문에 추가/삭제가 용이하다.

 - 처음, 끝, 중간에 엘리먼트를 추가/삭제 하는 기능이 있다.
 - 리스트에 데이터가 있는지를 체크하는 기능이 있다.
 - 리스트의 모든 데이터에 접근할 수 있는 기능이 있다.

 

 

연결리스트의 종류에는 단일 연결 리스트, 원형 연결 리스트, 이중 연결 리스트가 있다.

1. 단일 연결 리스트

 - 하나의 노드는 데이터 필드와 링크 필드로 구성된다.

 - 데이터 필드는 데이터를 저장하고 링크 필드는 다음 노드의 주소를 저장한다.

 - 마지막 노드(tail)의 링크필드는 null이다.

 - 단방향으로 연결된 리스트이다.

 

2. 원형 연결 리스트

 - tail의 링크 필드는 맨 앞의 노드(head)이다.

 - head 앞에 노드를 삽입할 경우 tail의 링크 필드를 수정해 주어야 한다.

 - 단방향으로 연결된 리스트이다.

 

3. 이중 연결 리스트

 - 단일 연결 리스트나 원형 연결 리스트는 현재 노드의 이전 노드를 접근하기 위해서는 리스트를 순회해야 한다.

 - 위 단점을 보완하기 위해 이전 노드의 주소를 저장한 것이 이중 연결 리스트이다.

 - 양방향으로 연결된 리스트이다.

 - 링크 필드는 이전 노드의 주소를 저장하는 Left Link Field와 다음 노드의 주소를 저장하는 Right Link Field를 가지고 있다.