Linked List 연결 리스트 / Queue 큐 / Stack 스택

춘식이

Linked List란?

'Node' 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조이다.

노드(Node)에는 데이터 값 + 다음 노드의 주소값이 저장되어 있다.

(양방향 링크드 리스트의 경우 노드에서 이전 노드의 주소값도 가지고 있음.)

Array List의 경우 데이터의 연속성을 유지하기 위해서 메모리에 순차적으로 데이터를 저장했지만,

연결 리스트는 다음 노드의 주소 정보를 통해서 연결되어 있기 때문에 물리적으로는 비연속적이지만,

논리적으로는 연속성을 유지하고 있다.

 

-> Array List는 데이터가 메모리에 쫙 붙어 있지만, Linked List는 메모리상에서 연속성을 유지하지 않아도 되기 때문에

(메모리 내에서 노드가 따로 따로 떨어져 있기 때문에) 메모리 공간의 사용이 더 자유롭다.

하지만 Array List에서는 데이터만 있으면 됐는데, Linked List의 노드에는 데이터 뿐만 아니라 

이전/이후 노드의 주소값도 가지고 있어야 되기 때문에 노드 당 차지하는 메모리가 더 크다.

 

내부 코드 구현에서 head, current, tail의 개념을 사용할 수 있음.

주요 기능으로는

- append(노드 추가)

- get (노드 값 얻기)

- insert_back(마지막에 노드 추가)

- insert_front(맨 앞에 노드 추가)

- insert_at(중간에 노드 추가)

- remove_back(마지막 노드 제거)

-remove_front(맨 앞 노드 제거)

-remove_at(중간 노드)

등이 있다.

 

기본적으로 인덱스를 활용할 수 있고, 

head(맨 앞 노드를 가리키는)

current(노드를 타고 타고~)

tail(마지막 노드를 가리키는)의 개념을 활용 할 수 있다.

(시간 복잡도를 줄이기 위해서, tail이 없다면 하나씩 노드를 다 타고 가봐야 할테니)

 

새로운 노드를 만들거나, 기존 노드를 제거할 때

해당 노드의 앞 뒤 노드의 연결성을 고려해줘야 한다.

 

단방향 연결 리스트(Singly Linked List)

노드가 다음 노드의 주소만 가지고 있음. 

 

양방향 연결 리스트(Doubly Linked List)

노드와 노드가 서로 연결되어 있음.

노드가 이전 노드와 다음 노드의 주소를 가지고 있음.

 

원형 연결 리스트(Circular Linked List)

마지막 노드가 첫번 째 노드를 가리키는 연결 리스트 

---

큐(Queue)

선입 선출! (FIFO - First In First Out)형식으로 데이터를 저장하는 자료구조

 

큐의 맨 앞을 front, 맨 뒤를 rear라고 한다면

front에 데이터를 추가하는 것을 enqueue,

rear에서 데이터를 꺼내는 것을 dequeue라고 함.

 

Array List 베이스, Linked list 베이스 로 구현 가능하지만

Array List로 구현 할 경우, dequeue에서 시간 복잡도가 O(n)이 되는 문제가 있어서

Linked List 베이스로 구현하는 것이 더 나을 수 있다.

 

-> Array List의 경우, deqeue를 하면 데이터들을 앞으로 한 칸 씩 다 땡겨줘야 하기 때문에(n만큼)

시간 복잡도가 O(n)이 되는 것.

대신 파이썬의 기본 List를 활용하면 enqueue는 append로, dequeue는 pop(0)으로 구현할 수 있어서 간단하기는 함.

 

반면 Linked List로 구현하면 그냥 맨 앞 노드를 제거하면 그만이다.

구현은 좀 더 복잡하겠지만... 하지만 아래의 덱을 사용하면 생각보다 간단하게 구현할 수 있다!

덱(Deqeue)

Double ended queue을 줄인 표현으로 덱 자료구조라고 한다.

 

기본 큐는 뒤에서 enqueue, 앞에서 dequeue하지만

덱에서는 앞에서 enqueue, dequeue가 가능하고

맨 뒤에서도 enqueue, dequeue가 가능하다.

-> 양방향 enqueue, dequeue가 가능하다는 얘기.

 

파이썬에서는 기본적으로 

from collections import dequeue로 바로 쓸 수 있다.

(내부적으로 Doubly Linked List로 구현되어 있음)

 

큐가 단독으로 출제되기 보다는, bfs에서 자주 쓰이는 개념이라고 함!

스택(Stack)

후입선출! (LIFO - Last In First Out)

가장 마지막에 추가된 데이터가 먼저 나오는 형식으로 데이터를 저장하는 자료구조.

보통 vertical bar( I 모양)형태로 많이 설명이 되고,

스택의 맨 위(top)에 데이터를 추가하는 것을 push

스택의 맨 위(top)에서 데이터를 추출하는 것을 pop 이라고 함.

 

네비게이션 방식에서 뷰를 푸쉬, 팝 하는 것도 스택!

스택이 꽉 차서 더이상 데이터를 추가하지 못해, 넘쳐 흘러 문제가 생기는 것이 Stack Overflow

 

Array List, Linked List로 구현할 수 있지만,

Array List로 구현하는 것이 간편하다.

 

파이썬을 기준으로, 기본 List를 활용하면 그냥 이것이 가장 심플한 스택이 된다.

push는 append로, pop은 pop으로..

그냥 이게 스택 그 자체..

 

* 자료구조, 알고리즘 관련 개념들을 익히는 목적으로 공부를 시작하고 있기 때문에 소스코드 및 관련 문제는 제대로 다루지 않았다.