3장. 심화된 자료구조

실습_3. 심화된 자료구조

연결리스트

• Linked List
• 여러개의 노드들이 한 줄로 연결
• 노드 = 저장할 데이터 + 다음 노드로의 연결

단순 연결 리스트

• 기본리스트
• 한 방향으로 만 이어진 연결 리스트

이중 연결 리스트

• 양쪽 방향으로 이어진 연결 리스트
• 다음노드로의 열결
  • 꼭 한 데이터를 가르키지 않아도 된다

원형 연결 리스트

• 가장 뒤의 노드가 맨 앞의 노드에 연결된 연결 리스트

기타 연결 리스트

• 아무 형태의 연결 리스트 모두 가능

배열 VS 연결 리스트

• 배열: 인덱스 이용해서 데이터 접근
• 연결 리스트: 현재 노드에서 연결된 노드로만

헤드 Heal

• 리스트는 시작과 끝이 정해져 있다

연결 리스트 시간 복잡도

• 자료 중간데 추가/삭재 : O(1)
• 배열 시간 복잡도와 비교해보면 : nums.insert(3,9) : O(N)

큐

• 먼저 줄 선 사람이 먼저 나간다
• FIRST IN FIRST OUT(FIFO)

큐 시간 복잡도

• 입력하기 : O(1)
• 출력하기 : O(1)

큐 in Python

• queue library 활용

```import queue

q = queue.Queue() q.put(2) q.put(8) q.get()

* 배열을 큐(Queue)로 활용

q = [8, 19, 37, 4, 5]

q.insert(0, 2) # 맨 앞에 입력한다 q.pop() # 맨 뒤에서 가져온다

queue 라이브러리와 비교했을때 시간복잡도가 크다

# 스택

* 나중에 줄 선 사람이 먼저 나간다
* LAST IN FIRST OUT(LIFO)

## 스택 시간 복잡도

* 입력하기 : O(1)
* 출력하기 : O(1)

## 스택 in Python
* 배열을 스택으로 활용

```python
Stack = []
Stack.append(2)
Stack.append(5)
Stack.pop() #5를 반환