Linked List 정리

참고영상(https://www.youtube.com/watch?v=K1PlysPgNZY), (코딩문, 연결리스트 (Linked List) 쉽게 이해하기)

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

Node는 무엇?

• 데이터 덩어리
• 데이터(data), 링크/포인터 역할을 하는 next가 담김.

배열과 연결 리스트의 차이점

• 배열
  순차적으로 연결되어 있는 구조.
  random access 가능
  배열의 n번째 원소 방문시 O(1) 시간으로 가능
  원소의 삽입&삭제가 일반적으로 O(n)소요됨.

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

연결리스트의 종류
1. Singly Linked List(단일 연결 리스트)

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

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