선형 자료구조 - 배열, 연결 리스트, 스택, 큐

1. 배열 (Array)

*삽입/삭제의 시간복잡도 O(N)

  -N개의 인덱스가 있을 때 맨 앞에 삽입할 경우 하나씩 전부 뒤로 밀려야 하기 때문에 N

*탐색의 시간복잡도 O(1)

  -원하는 인덱스에 바로 접근이 가능하기 때문에 상수.

*파이썬에서는 size 변경이 가능.

 

2. 연결 리스트 (Linked list)

두 부분으로 이루어진 리스트.

data가 저장되어 있는 부분과 다음 데이터를 가리키는 포인터가 저장되어있는 link 부분으로 나뉘어 있다.

단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다.

*삽입/삭제의 시간복잡도는 O(1)

- 연결부분만 명시하면 된다.

*탐색의 시간복잡도 O(N)

- 어떤 자료를 찾으려면 링크를 타고타고 들어가야 한다.

 

3. 스택 (Stack)

- 후입선출 구조

- 따라서 자료의 위치를 명시할 필요가 없음. Push, Pop 구조임.

- Push 하고 Pop하면 가장 나중에 들어온 데이터가 삭제됨.

 

4. 큐 (queue)

- 선입선출 구조

- 줄서기와 같다. 가장 먼저 들어간 데이터가 가장 먼저 삭제된다.

- 파이썬에서 큐가 필요하면 deque를 임포트해서 쓰면 된다. queue는 느리다.

from collections import deque

dq = deque()
dq.append(123)
dq.appendleft(456)
dq.appendleft(789)
print(dq)

print(dq.pop())
print(dq.popleft())

이렇게 하면 deque( [789], [456], [123] ) 이 되고 pop() 하면 [123]이 삭제되고 popleft() 하면 [789]가 삭제됨.