연결 리스트 (Linked List)
- 다른 추상 자료형을 구현할 때 기반이 되는 기초 선형 자료구조
- 선형 배열과 비슷하지만, 링크라고 부르는 고리로 원소리들이 연결되는 점이 다르다
- 장점
- 원소를 삽입, 삭제하는 것이 쉬움 (빠름)
- 단점
- 데이터 구조 표현에 소요되는 저장 공간(메모리) 소요가 크다
- k 번째 원소를 찾는데 배열보다 시간이 오래 걸림
(배열은 데이터 원소들이 번호가 있는 칸에 있지만, 연결 리스트는 연결된 형태)
- 종류
- 단방향 연결 리스트 (Singly Linked List)
- 양방향 연결 리스트 (Doubly Linked Lists)
- 원형 연결 리스트 (Circular Linked List)
양방향 연결 리스트 (Doubly Linked Lists)
- 노드들이 앞/뒤로 연결되어 있음
(인접한 두 개의 노드가 앞의 노드로부터 뒤의 노드가, 뒤의 노드로부터 앞의 노드로 연결) - 리스트의 맨 앞과 맨 뒤에 .더미 노드(dummy node)를 하나씩 추가 가능
- 장점
- 데이터 원소를 차례로 방문할 때, 앞에서부터 뒤로도 가능하지만 뒤에서부터 앞으로도 가능
(컴퓨터 운영체제(operating system)에서 리스트를 대상으로 앞/뒤로 왔다 갔다하는 작업이 많아 용이)
- 데이터 원소를 차례로 방문할 때, 앞에서부터 뒤로도 가능하지만 뒤에서부터 앞으로도 가능
- 단점
- 링크를 나타내기 위한 메모리 사용량 증가
- 원소의 삽입/삭제하는 연산에 있어 복잡(프로그래머가 귀찮아짐)
스택 (Stack)
- 데이터 원소들을 끄집어내면 마지막에 넣었던 것부터 넣은 순서의 역순으로 꺼내지는 자료구조
- 후입선출 (LIFO - Last in First Out) 자료구조
- 스택에 데이터를 추가하는 동작 = 푸시 (push)
- 마지막에 추가되었던 원소를 꺼내고 삭제하는 동작 = 팝 (pop)
- 기초 연산 동작
- size() : 현재 스택에 들어 있는 데이터 원소의 수를 구함
- isEmpty() : 현재 스택이 비어 있는지를 판단
- push(x) : 데이터 원소 x를 스택에 추가
- pop() : 스택에 가장 나중에 저장된 데이터 원소를 반환하고 제거
- peek() : 스택에 가장 나중에 저장된 데이터를 반환하고 제거하지 않음
728x90
'ssung_데이터 엔지니어링 > 1주차_자료구조, 알고리즘' 카테고리의 다른 글
DFS/BFS (Depth-First Search / Breadth-Frist Search) (1) | 2023.10.20 |
---|---|
해시 (Hash)와 람다 (Lambda) (1) | 2023.10.19 |
큐 (Queue)와 트리 (Trees), 힙 (Heaps) (1) | 2023.10.18 |
탐색(Search)와 재귀 알고리즘(Reculsive algorithms) (0) | 2023.10.16 |