[alice] 심화된 자료구조

알고리즘을 위한 자료구조

[3장 심화된 자료구조]

연결 리스트(Linked List)

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

 

1) 단순 연결 리스트

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

 

2) 이중 연결 리스트

양쪽 뱡향으로 이어진 연결 리스트

※ 다음 노드로의 연결 -> 꼭 한 데이터를 가르키지 않아도 ㄱㅊ

 

3) 원형 열결 리스트

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

 

4) 기타 연결 리스트

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

 

 

[배열 vs 연결 리스트]

배열: 인덱스를 이용해서 데이터 접근

연결 리스트: 현재 노드에서 연결된 노드로만

 

head: 시작노드

tail: 끝 노드

None: 마지막노드(노드가 더이상x)

 

 

[시간 복잡도]

자료 중간에 추가/삭제 : O(1)

 

(노드 삭제)

 

 

큐

• FIFO(FIRST IN FIRST OUT)
• 입력/출력: O(1)
• 효율적이라 많이 쓰이는 자료구조

 

[python library 활용]

import queue

q = queue.Queue()

q.put()    # 값 넣기

q.get()    # 값 하나 빼고 큐 조절

 

(배열을 큐로 활용)

q = [8, 4, 5, 2, 9]

q.insert(0, 2)   # 맨 앞에 입력

q.pop()          #  맨 뒤에서 가져옴

배열을 활용했을 때 시간 복잡도에서 문제점을 가짐

 

 

(스트리밍 데이터의 이동 평균)

 

 

스택

• SLFO(LAST IN FIRST OUT)
• 입력/출력: O(1)

(스택 in python)

배열을 스택(stack)으로 활용

 

Stack = []

Stack.append()   # 추가

Stack.pop()     # 반환

 

 

[실습- 괄호 매칭]