[자료구조] List, Array

동일한 특성의 데이터들의 집합을 가리키는 자료구조를 표현하는 방법에는 배열 (Array)와 리스트 (List)가 있습니다.

List

List의 특징과 종류

배열을 문제점을 해결하기 위한 자료구조
1. 순서가 있는 데이터의 모임
2. 빈 공간은 허용하지 않음 : 삭제 시, 가용 메모리로 변경됨

• 언어별 리스트 지원

  • JavaScript : 배열에 리스트 기능 포함
  • Python : 기본적으로 리스트, 배열을 따로 지원하지 않음
  • java : 배열, 리스트 모두 지원 (ArrayList와 LinkedList로 나뉨)
  • C : 리스트 지원하지 않음

• ArrayList와 LinkedList

1. ArrayList
   • 배열을 사용하여 리스트를 구현함
   • 랜덤 엑세스 가능
   • 사이즈가 고정되어 있음
   • 삽입 시에는 사이즈를 늘려주어야 함 (연산 추가)
   • 삭제 시에는 빈 인덱스를 채워야 함 (연산 추가)
   • 지속적 삭제시에 낭비되는 메모리가 많으므로 지속적으로 삽입, 삭제가 발생하는 경우에 사용이 적합하지 않음
2. LinkedList
   • 연결 형태로 연결이 가능함
   • 순차적 엑세스만 가능함
   • 자료들을 저장공간에 불연속적인 단위로 저장함

Array

Array의 특징

고정된 크기를 갖는 동일한 자료형의 원소들이 연속적(논리적, 물리적 저장 순서 일치) 형태로 구성된 자료구조
1. 인덱스에 따라 값을 유지 : 데이터가 삭제 되어도 메모리가 낭비
2. 처음 배열을 선언할 때, 크기를 지정 (더 적은 데이터를 저장하더라도 실제 배열의 크기는 처음 선언한 크기와 동일)

• 인덱스 : 각 데이터의 0번부터 시작하여 해당 원소에 접근
• 랜덤 엑세스가 가능 : 접근, 수정 O(1)로 빠르게 조회가 가능함
• 삽입, 삭제 시 : 형태 유지를 위해서 shift 연산을 해야함, O(n)

List와 Array의 차이점

List와 Array의 장단점

List

장점

• 삽입, 삭제 시에 효율적 (노드의 참조 관계 수정)
• 크기가 자유로움
• 메모리 재사용 가능 (삭제 시, 해당 노드는 가용 메모리로 전환)

단점

• 구현이 배열에 비하여 복잡함
• 데이터 검색 시에 순차적 검색으로 비효율적
• 참조를 위한 메모리가 따로 필요함

Array

장점

• 리스트에 비하여 구현이 쉬움
• 검색이 효율적 (인덱스가 있기 때문에)
• 연속된 메모리 공간의 할당으로 순차 접근이 가능함
• 참조를 위한 메모리가 따로 필요하지 않음

단점

• 삽입, 삭제 시에 비효율적
• 크기가 지정되어 있음 (선언 시에 지정)
• 메모리 재사용 불가 (삭제 시, 가용 메모리로 전환되지 않음, 공간 차지)

리스트 또는 배열을 선택하는 법

참조
1. 배열과 리스트의 차이
2. 비교-배열과 리스트의 차이
3. Do it ! 자료구조와 함께 배우는 알고리즘 입문