[자료구조] 2-1 연결리스트 / 큐 / 스택

1. 연결리스트

연결리스트는 각각의 노드가 모여서 이루어진다. 하나의 노드는 data와 link로 이루어져 있다. link는 데이터가 작동하는 방향을 나타낸다.

 

 

1-1 배열(array)과의 비교

이해를 위해 일반적 배열과 비교해보자

배열
- random access 가능 (index가 있음)

- 메모리에 저장될 때 연결되어 저장됨
- 선형 검색을 통하기 때문에 삽입 삭제에 O(n)이 걸림

연결리스트
- random access 불가능 (index 없음)

- 메모리에 노드별로 산발적으로 저장됨. link가 있기에 다음 노드를 알 수 있음
- 삽입 삭제에 O(1)이 걸림. 굉장히 빠름

 

 

2. 스택과 큐

스택과 큐 모두 배열이되 어떤 규칙을 갖는 것으로 둘다 '추상적 자료구조'다. 또한 둘다 연결리스트의 한 종류다.

 

2-1 스택

스택

배열이 수직으로 쌓여있는 구조. 그러므로 맨 위에는 가장 최근의 아이템이 쌓아져있고, 삭제할 때 맨 위에 있는 것부터 삭제. 팬케익 먹기를 상상하면 된다. 컴퓨터에서 컨트롤z(실행취소)  또는 브라우저에서 뒤로가기 등의 상황에 쓰인다.

2-2 큐

선입선출. 가장 먼저 들어온 아이템부터 삭제한다. 쇼핑몰 주문 처리, 이메일 전송 등 먼저 요청이 된 것부터 처리하는 시스템에서 사용된다.