배열과 연결리스트, 덱(deque) 자료구조

배열

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

 

장점 

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

 

단점 

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

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

 

연결 리스트 

값과 주소를 묶은 노드를 주소로 연결한 자료구조이다.

 

장점
1. 주소로 연결되어 있어 값을 삽입하거나 삭제하는 연산의 속도가 빠르다.
2. 선언할 때 크기를 별도로 지정하지 않고 주소로 계속 연결해 나가며, 연속된 공간이 필요하지 않아 빈 공간을 활용할 수 있어 메모리 활용이 효율적이다.

 

단점
1. 리스트 원소로 바로 접근이 불가능하다. Head주소부터 차례대로 순차접근을 해야 한다.

 

 

덱(deque)

위 그림과 같이 자료구조의 왼쪽 부분과 오른쪽 부분 즉 양쪽 모두에서 자료의 삽입과 삭제 가 가능한 자료구조이다.

1. append() :  오른족 부분에 자료 추가

from collections import deque dq = deque()
dq.append(1)
dq.append(2)
dq.append(3)
print(dq) #출력 [1, 2, 3]

 

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

from collections import deque 
dq = deque() 
dq.appendleft(1) 
dq.appendleft(2) 
dq.appendleft(3)
print(dq) #출력 [3, 2, 1]

 

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

from collections import deque 
dq = deque()
dq.append(1)
dq.append(2)
dq.append(3) 
dq.popleft() 
print(dq)   #출력 [2, 3]

 

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