[알고리즘 위한 한발짝 두발짝🐾] 연결리스트 (Linked List)

<본 블로그는 코딩문 codingmoon 님의 유튜브를 참고해서 공부하며 작성하였습니다 :-)>

=> 빅오(Big-O)표기법 쉽게 이해하기 [10분 정리]

 

🫧 연결리스트 (Linked List) 

: 연속된 노드(Node) 의 연결체

 

🐾 노드(Node)

: 연결 리스트에서 사용되는 하나의 데이터 덩어리

: 데이터 & 링크, 2가지의 필드를 담고 있는 구조

 

🐾 data

: 노드가 담고 있는 데이터/값

 

🐾 next

: 링크/포인터 역할, 다음 노드의 주소를 저장

(양방향 연결 리스트, prev 포인터 (이전 노드의 주소) 추가)

 

🫧 연결리스트 (Linked List) vs 배열

연결리스트 (Linked List)	배열
random access 불가능	random access 가능
리스트의 n번째 노드 방문시 O(n) 시간 소요	배열의 n번째 원소 방문시 O(1) 시간으로 가능
배열보다 빨라질 수 있는 노 삽입 & 삭제	원소 삽입 & 삭제 일반적으로 O(n) 시간 소요

 

🫧 연결리스트 (Linked List)  종류

- Singly Linked List (단일 연결 리스트)

: 다음 노드의 대한 point 가짐

: 한쪽 방향으로 흐름

 

- Doubly Linked List (이중 연결 리스트)

: 다음 노드 _ 이전 노드의 pont 가짐

: 앞뒤로 탐색 가능

: 노드마다 2개의 point 가져서 복잡

 

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

: 마지막이 head 를 가르킴