3월 2주차 자료 구조(5.2 선형 자료 구조)

[K-J-HYEON]

연결 리스트, 배열, 벡터

선형 자료 구조

5.2.1 연결리스트

Node를 활용해서 링크드리스트 트리 등 다양하게 구현이 가능하다.

(python)
class Node:
	def __init__(self, value = 0, next = None):
		self.value = value
		self.next = next

first = Node(1)
second = Node(2)
third = Node(3)
first.next = second
second.next = third
first.value = 6

LinkedList 틀

(python)
class LinkedList(object):
    def __init__(self):
        self.head = None
    def append(self, value):
        pass
    
    def get(self, idx):
        pass
    
    def insert(self, idx, value):
        pass
    
    def delete(self, idx):
        pass

Linked List 구현

(python)
class LinkedList(object):
    def __init__(self):
        self.head = None

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node

        # 맨 뒤의 node가 new_node를 가리켜야 한다.
        else:
            current = self.head
            while(current.next):
                current = current.next
            current.next = new_node

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(4)

get

(python)
class LinkedList(object):
    def __init__(self):
        self.head = None

    def append(self, value):
        pass

    def get(self, idx):
        current = self.head
        for _ in range(idx):
            current = current.next
        return current.value

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(4)
ll.get(0)
ll.get(1)
ll.get(3)

remove

(python)
class LinkedList(object):
    def __init__(self):
        self.head = None

    def append(self, value):
        pass

    def remove(self, idx):
        pass
    
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(4)
ll.append(5)
ll.remove(3)

insert_back()

• O(1)

(python)
class LinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        # 맨 뒤의 node가 new_node를 가리켜야 한다.
        else:
            self.tail.next = new_node
            self.tail = self.tail.next

ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.append(4)

⇒ 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조입니다. 삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸린다.

prev 포인터 , next 포인터

⇒ 앞과 뒤의 노드를 연결시킨 것이 연결 리스트

⇒ 맨 앞에 있는 노드를 헤드(head)

• 싱글 연결 리스트 ⇒ next 포인터만 가진다.
• 이중 연결 리스트 ⇒ next 포인터와 prev 포인터를 가진다.
• 이중 연결 리스트 push_front(), push_back, insert()등의 함수가 있다.
• 원형 이중 연결 리스트 ⇒ 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리킨다.

5.2.2 배열(ArrayList)

List ↔ (Set)

Python에서 Arraylist는 이미 List 로 구현이 되어있다.

배열은 선언시에 size를 정하여 해당 size만큼의 연속된 메모리 할당 받아 data를 연속적/순차적으로 저장하는 자료구조

int arr[5] = {3,7,4,2,6}
// size가 5인 int형 배열 선언

• 배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터 모은 집합
• 중복을 허용하고 순서가 있다.
• 정적 배열기반 설명
• 탐색에 O(1)이 되고
• 랜덤 접근(random access)이 가능
• 삽입, 삭제 O(n)이 걸린다.
• 데이터 추가, 삭제 ⇒ 연결 리스트이 유리
• 탐색 ⇒ 배열이 유리
• 배열 ⇒ 인덱스에 해당하는 원소 빠르게 접근 또는 데이터 쌓고 싶을 때 사용
• 순차적 접근, 랜덤 접근은 아래와 같다.

배열 / 연결 리스트

• 배열은 상자를 순서대로 나열한 데이터 구조
• 몇 번째 상자인지만 알면 상자의 요소를 끄집어낼 수 있다.
• 연결 리스트는 상자를 선으로 연결한 형태의 데이터 구조, 상자 안의 요소 알기 위해 하나씩 상자 내부 확인해봐야 함

• 탐색은 배열이 빠르고 연결 리스트는 느림
• 배열의 경우 상자 위에 있는 요소 탐색하면 됨
• 연결 리스트는 상자를 열어야 하고
• 선을 기반으로 순차적으로 열어야 한다.
• 데이터 추가 및 삭제는 연결리스트가 더 빠르고 배열이 느림
• 배열은 모든 상자를 앞으로 옮겨야 추가 가능
• 연결 리스트는 선을 바꿔서 연결해주기만 하면 됨

5.2.3 벡터

• 벡터는 동적으로 요소를 할당할 수 있는 동적 배열
• 컴파일 시점에 개수 모르면 벡터 써야한다.
• 중복을 허용하고 순서가 있고 랜덤 접근이 가능
• 탐색과 맨 뒤의 요소를 삭제, 삽입하는 데 O(1)이 걸림, 맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는 데 O(n)의 시간 걸림
• 뒤에서부터 삽입하는 push_back() / O(1)의 시간 걸림
• 벡터의 크기가 증가되는 시간 복잡도가 amortized 복잡도, 상수 시간 복잡도 O(1)과 유사한 시간 복잡도를 가지기 때문
• push_back()을 한다 해서 매번 크기가 증가하는 것이 아니라 2의 제곱승 + 1마다 크기를 2배로 늘림
• ci를 i번째 push_back()을 할 때 드는 비용(cost)이라 하면 ci는 1 또는 1 + 2**k라는 것을 알 수 있다. n번 push_back()을 한다 했을 때 드는 비용 T(n)은 아래와 같다.

뒤부터 요소를 더하는 push_back(), 맨 뒤부터 지우는 pop_back(), 지우는 erase(), 요소를 찾는 find(), 배열을 초기화하는 clear() 함수가 있다. - 두개의 코드는 같은 코드 - 벡터의 요소를 순차적으로 탐색 - v에 pair라는 값이 들어가면 for (pair a : v) 방식으로 순회

5.2.4 스택

• LIFO(Last In First Out) : 스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질을 가진 자료 구조
  • 재귀적인 함수, 알고리즘에 사용
  • 웹 브라우저 방문 기록 등에 쓰임
  • 삽입 및 삭제 O(1), 탐색 O(n)

5.2.5 큐

• FIFO(First In First Out) : 큐는 먼저 집어넣은 데이터가 먼저 나오는 성질을 지닌 자료 구조
  • 삽입 및 삭제 O(1), 탐색 O(n)
  • CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용

<출처 및 참고 : 면접을 위한 CS 전공지식 노트 - 주홍철 >