자료구조 - 배열(Array)과 리스트(List) 그리고 벡터(Vector)

배열(Array)

 

배열은 연속적인 메모리에서 같은 종류의 아이템들을 저장할 수 있는 자료구조이다.

배열에 1, 2, 3, 4, 5라는 숫자를 입력하고 컴퓨터 1개의 메모리공간이 1개의 사각형이라고 했을 때, 아래 그림처럼 표현할 수 있다.

 

 

연속된 메모리 블록에 저장되므로 인덱스를 통해 빠르게 접근이 가능한 장점이 있다.

 

 

그.런.데 저 5개의 메모리공간에 '6'이라는 숫자를 append 하려고 한다면?

배열은 고정된 크기를 가지며, 나중에 크기를 늘릴 수 없다.

만약 크기를 늘려야 한다면, 새로운 배열을 만들어 기존 데이터를 복사해야 한다. 아래 그림처럼 말이다.

 

이렇게되면 4개의 메모리공간이 남게되고, 메모리공간에 관하여 효율적이지 못한 단점도 있다. 

 

따라서, 배열의 크기를 동적으로 관리하기 위해서는 ArrayList와 같은 동적 자료 구조를 사용하는 것이 일반적이다.

 

참고..

JavaScript의 배열은 크기가 동적으로 변경된다. 배열의 크기를 미리 정해두지 않아도 되고, 배열의 요소를 추가하거나 제거할 수 있다.

 

리스트(List)

리스트는 2가지 종류가 있는데 Linked List와 Array List가 있다.

 

 

Linked List

각 요소가 다음 요소에 대한 포인터를 가지는 노드들로 이루어진 자료구조이다.

1, 2, 3, 4, 5라는 linked list는 메모리공간에서 연속적이지 않으며 노드를 연결시키는 형태로 구현된다.

연속적이지 않아 인덱스를 통해 접근할 때 배열보다는 시간이 조금 걸린다는 단점이 있다.

 

 

그.런.데 저 5개의 메모리공간에 '6'이라는 숫자를 append 하려고 한다면?

그냥 1개의 메모리 공간에 숫자 '6'을 넣어주고 노드를 연결시키면 된다. 따라서 메모리공간에 관하여 배열보다 효율적이다.

 

그리고 마지막 요소는 tail이 된다.

Linked List는 head와 tail로 처음과 끝을 구분하기 때문에 만약 요소를 찾는다면, head부터 시작해 이동해서 봐야하기 때문에 배열과 달리 시간이 걸리는 것이다.

 

사실 Linked list 안에 또 3가지 확장팩들이 있다. circular linked list, doubly linked list, circular doubly linked list 이다.

그림으로 간단하게 표현하자면 다음과 같다. (방향에 포커스를 맞추기!)

 

• circular linked list

 

 

• doubly linked list

 

 

• circular doubly linked list

 

 

 

 

Array List

Array List는 Array와 Linked list의 장점만 모아놓은 것이라 생각하면 간단하다.

 

배열처럼 요소들이 연속된 메모리 공간에 저장되므로 인덱스를 사용하여 빠르게 접근할 수 있다.

Array List는 내부적으로 배열(Array)을 사용하지만 배열의 경우 크기가 고정되어 있어 추가로 넣으려면 크기를 다시 만들어줘야 하는데 Array List는 자동적으로 크기가 조정된다. (배열의 초기크기는 기본적으로 10개정도이다.)

 

자동적으로 크기를 조정해준다는 건,

배열이 꽉 차서 더 이상 요소를 추가할 수 없을 때, ArrayList는 자동으로 크기를 늘린다. 보통 현재 크기의 1.5배 또는 2배로 크기를 늘린다.

따라서 요소가 추가될 때만 크기가 조정되므로, 일반적으로 메모리를 효율적으로 사용할 수 있다.

 

 

Array list와 함께 비교되는 것이 있는데 Vector이다. 둘 다 자바에서 제공하는 동적 배열 클래스이다.

특징	Array List	Vector
동기화	동기화 X	동기화 O
성능	상대적으로 빠름	상대적으로 느림
확장 방식	50%씩 증가	100%씩 증가
초기 릴리스	JDK 1.2	JDK 1.0
Thread 안정성	단일 스레드 사용 권장	여러 스레드에서 안전하게 사용 가능

 

Vector는 동기화되어 멀티스레드 환경에서 안전하지만, 성능이 약간 떨어지며, ArrayList는 동기화되지 않아 단일 스레드 환경에서 더 나은 성능을 제공한다.

 

 

Summary

특징	Array List	Linked List	Vector
동기화	X	X	O
임의 접근	허용	허용안함	허용
메모리 위치	연속	연속 X	연속
삽입삭제	느림	빠름	느림

 

 

아래는 배열, 리스트, 집합(Set), 맵(Map) 자료구조 비교표이다.

특징	배열 (Array)	리스트 (List)	집합 (Set)	맵 (Map)
개념	고정 크기의 연속적인 요소 저장 공간	동적 크기의 요소 저장 목록	고유한 값들의 집합	키-값 쌍(Key-Value Pair) 저장
중복 허용	허용	허용	허용하지 않음	Key는 중복 불가, Value는 중복 허용
순서 보장	저장된 순서 유지	저장된 순서 유지	순서 보장 안됨	파이썬 3.7부터 삽입 순서 유지
인덱싱	인덱스로 요소에 접근 가능	인덱스로 요소에 접근 가능	인덱싱 불가	인덱싱 불가, 키로 값에 접근 가능
시간복잡도	O(1), O(n)	O(1), O(n)	O(1) ~ O(log n)	O(1) ~ O(log n)
사용 예	고정된 크기의 데이터를 처리할 때	동적 크기 데이터를 순차적으로 처리할 때	유일한 항목을 관리할 때	키와 값을 매핑하여 데이터를 처리할 때
구현	array.array	list	set	dict
파이썬 메소드	append(), extend(), index(), pop()	append(), extend(), insert(), remove(), pop()	add(), remove(), discard(), union(), intersection()	get(), keys(), values(), items(), update()

 

이때 배열은 고정된 크기라고 했는데 append()는 어떻게 작용하는걸까?

import array

# 정수형 배열 생성
arr = array.array('i', [1, 2, 3, 4, 5])

# 배열에 요소 추가
arr.append(6)

#출력
array('i', [1, 2, 3, 4, 5, 6])

 

arr 배열에는 리스트를 포함하고 있다.

따라서 리스트는 동적으로 크기를 조절할 수 있기 때문에, 고정 크기 배열에서 불가능한 append 작업이 가능한 것이다.