[자료구조] 2~5 주차 노트 (시간복잡도, Linked List, Stack, Queue)

KOCW에서 제공하는 고려대학교 유용재 교수님의 자료구조 강의를 수강한 후, 정리한 글입니다. 

http://www.kocw.net/home/cview.do?cid=b216fbe96107c9ea

자료구조

 

강의 주제

• 2주차 시간복잡도의 이해
• 3주차 Linked List와 연결형 자료구조
• 4주차 Stack 자료구조의 이해와 응용
• 5주차 Queue와 환형 Queue

 

정적 배열과 동적 배열

정적 배열 : 자료구조의 한 형태인 배열에 속하며, 그중에서도 크기가 고정되어있는 것.

배열의 특징인 인덱스를 활용한 접근, 원소간 순서 구분을 공유

정적 배열의 한계? 크기가 고정되어있어 확대 어려움

동적 배열 List

동적 배열 : 자료구조의 한 형태인 배열에 속하며, 그중에서도 크기가 가변적인 것.

배열의 공간이 부족해질 경우, 크기를 2배 늘리는 방식으로 데이터를 제어

정적 배열과 동일하게 배열의 특징인 인덱스를 활용한 접근, 원소간 순서 구분을 공유

동적 배열에서 데이터 접근

- 배열은 인덱스를 이용하므로, 인덱스 값을 알면 데이터 값을 얻을 수 있음.

-> 데이터 접근 시간은 데이터 양 n과 무관. 시간 복잡도는 O(1)

동적 배열에서 데이터 말단 삽입

일반적으로 n과 무관하게 배열의 맨 앞 빈칸에 넣으면 되므로 O(1)

데이터가 다 차있는경우 삽입 시간 복잡도는? 

-> 배열을 복사, 2배 큰 배열 생성, 붙여넣기

-> O(n)

동적 배열에서 데이터 임의 위치 삽입

최악의 경우 모든 데이터를 1칸씩 이동해야함 -> 최악의 시간 복잡도 O(n)

동적 베열에서 데이터 삭제

말단 삭제 : O(1)
임의 위치 삭제 : 임의 위치 삽입과 동일한 원리로 최악의 경우 1칸씩 당겨야하므로 O(n)

데이터 접근 : [] OR list()

말단 삽입 : append()

임의 위치 삽입 : insert()

임의 위치 삭제 : del

 

Linked List

삽입/삭제가 많는 경우 동적배열은 비효율적.

연결형 자료 구조의 하나로, 각각의 데이터가 다음 데이터를 가리키는 형태의 자료구조.

각각의 원소는 Node라고 칭하며, 하나의 node는 data와 next 대상을 지님

편의상 linked list의 시작과 끝에는 data값을 가지지 않음(None). 더미 node를 배치

 

데이터 삽입시 O(1)

1) 신규 노드의 data, next 지정

2) 직전 node의 next를 신규 노드로 지정

 

삭제 시 직전 node를 안다는 가정 하에 시간 복잡도 O(1)

# Week 3

# Linked list

class Node:
    def __init__(self, data, prev, next):
        self.data = data
        self.prev = prev
        self.next = next
        
    
def node_insert(value, position):
    new_node = Node(value, position, position.next)
    new_node.prev.next = new_node
    new_node.next.prev = new_node
    return new_node
    
def node_delete(input_node):
    input_node.prev.next = input_node.next
    input_node.next.prev = input_node.prev

def visit_all(input_node):
    now_node = input_node
    while True:
        print(now_node.data)
        now_node = now_node.next
        if now_node.data == None:
            break
    
head = Node(None, None, None)
tail = Node(None, None, None)

head.next = tail
tail.prev = head


N1 = node_insert('A', head)
N2 = node_insert('B', N1)
N3 = node_insert('C', head)

node_delete(N2)

visit_all(head)

# result
'''
None
C
A
'''

# Week 4

# Stack

stack = list()

# push
stack.append(1)
stack.append(2)
stack.append(3)

# pop
stack.pop()

print(stack[-1])
print(stack)

# result
# 2
# [1, 2]

# Week 5

# Circular Queue

class CQueue:
    
    def __init__(self, size):
        self.size = size
        self.front = 0
        self.rear = 0
        self.data_list = list()
        for i in range(0, size):
            self.data_list.append(None)
    
    def enqueue(self, data):
        if (self.rear + 1 - self.front) % self.size == 0:
            print('Queue FULL')
        else : 
            self.data_list[self.rear] = data
            self.rear = (self.rear + 1) % self.size
            
            
    def dequeue(self):
        if (self.front == self.rear):
            print('Queue EMPTY')
        else : 
            self.data_list[self.front] = None
            self.front = (self.front + 1) % self.size


cq = CQueue(5) 

cq.enqueue('A')
cq.enqueue('B')
cq.enqueue('C')

cq.dequeue()

print(cq.data_list)

# result
# [None, 'B', 'C', None, None]​