[Python 코테 입문] 2. 배열, 연결리스트, deque

🖥️ 입문자를 위한 코딩테스트 핵심 - Python (김태원, 인프런)

 

섹션2. 배열, 연결리스트, deque

2-1. 배열(Array)

(1) 배열의 개념

배열(Array)은 같은 타입의 변수들로 이루어진 집합으로 메모리의 연속공간에 값이 채워져있는 형태의 자료구조다.

정수형 변수의 크기는 4byte이다.

정수형 변수로 이루어진 배열의 첫 번째 번지(array[0])의 메모리 주소가 100일 때, 각 번지의 메모리 주소는 차례대로 4byte씩 커진다.

(배열의 인덱스가 0, 1, 2, 3,...일 때 메모리 주소는 차례대로 100, 104, 108, 112,...가 된다.)

 

(2) 배열의 장단점

• 장점 

1. 검색 성능이 좋다. 인덱스를 사용하여 원소에 바로 접근할 수 있다.

(예) 위의 배열에서 9를 찾고자 한다. 인덱스를 사용해 값에 바로 접근하는 방식은 다음과 같다.

array[0]의 메모리 주소가 100이므로 array[3]의 메모리 주소는 100 + (3*4) = 112다.

배열 검색 시 연산량은 T(n) = 배열의 메모리 주소 + (인덱스 * 자료형 크기) 이다.

배열 검색 시 시간복잡도는 O(1) 이다.

 

• 단점

1. 메모리 활용이 비효율적이다. 초기 사이즈만큼 메모리의 연속공간이 필요하므로 작은 빈 공간은 버려지는 경우가 있다.

2. 값의 삽입과 삭제에서 비효율적이다. 데이터의 중간 지점에서 자료의 삽입, 삭제가 일어날 경우 다음 항목의 모든 값을 이동시켜야만 한다.

(예) 배열의 값들은 메모리 상에 연속적으로 존재하므로 중간에 자료가 삽입, 삭제될 경우 그 이후의 모든 값을 이동시켜야 한다.

입력크기가 n일 때 최악의 경우 n번 연산이 일어나야 한다.

배열의 값을 삽입 또는 삭제할 때 시간복잡도는 O(n) 이다.

 

2-2. 연결리스트(Linked List)

(1) 연결리스트의 개념

연결리스트(Linked List)는 값과 주소를 묶은 노드를 주소로 연결한 자료구조다.

첫 번째 노드의 주소를 가지고 있는 노드를 head라고 한다.

head를 제외한 각 노드는 값과 다음 노드의 주소를 가지고 있다.

 

(2) 연결리스트의 장단점

• 장점

1. 주소로 연결되어 있어 값을 삽입하거나 삭제하는 연산의 속도가 빠르다.

(예) 세 번째 노드에 7이라는 값을 가진 노드를 삽입한다.

두 번째 노드가 가리키는 주소를 330에서 320으로 바꾸고, 새로 삽입하는 세 번째 노드가 가리키는 주소를 330으로 지정해준다.

연결리스트에 값을 삽입하는 경우

 

(예) 세 번째 노드를 삭제한다.

두 번째 노드가 가리키는 주소를 330에서 400으로 바꾼다.

연결리스트의 값을 삭제하는 경우

연결리스트의 값을 삽입하거나 삭제하는 경우 시간복잡도는 O(1) 이다. 

 

2. 메모리 활용이 효율적이다. 선언할 때 크기를 별도로 지정하지 않고 주소로 계속 연결해나간다. 연속된 공간이 필요하지 않아 빈 공간을 활용할 수 있다.

 

• 단점

1. 검색 성능이 좋지 않다. 리스트 원소로 바로 접근이 불가능하며, Head 주소부터 차례대로 순차접근을 해야 한다.

연결리스트 검색 시 시간복잡도는 O(n) 이다.

 

2-3. deque(덱) 자료구조

Python에서 배열은 list 자료구조를 사용하고, 양방향 연결리스트는 deque 자료구조를 사용한다.

 

(1) deque의 개념

deque은 자료구조의 왼쪽 부분과 오른쪽 부분 즉 양쪽 모두에서 자료의 삽입과 삭제가 가능한 자료구조다.

따라서 자료구조의 왼쪽(앞쪽)에 값을 넣거나 빼야하면 deque를 써야 성능이 좋다. (시간복잡도 O(1))

list를 쓸 경우 왼쪽에 값을 넣거나 빼면 그 다음 모든 값을 이동시켜야 하므로 성능이 좋지 않다. (시간복잡도 O(n))

 

(2) deque의 내장함수

1. append() : deque의 오른쪽 부분에 자료 추가

from collections import deque
dq = deque()
dq.append(1)
dq.append(2)
dq.append(3)
print(dq)

deque([1, 2, 3])

 

2. appendleft() : deque의 왼쪽 부분에 자료 추가

from collections import deque
dq = deque()
dq.appendleft(1)
dq.appendleft(2)
dq.appendleft(3)
print(dq)

deque([3, 2, 1])

 

3. popleft() : deque의 맨 왼쪽 자료 제거

from collections import deque
dq = deque()
dq.append(1)
dq.append(2)
dq.append(3)
dq.popleft()
print(dq)

deque([2, 3])

 

4. pop() : deque의 맨 오른쪽 자료 제거

from collections import deque
dq = deque()
dq.append(1)
dq.append(2)
dq.append(3)
dq.pop()
print(dq)

deque([1, 2])