[LinkedList] 기본 정리

일반적인 LinkedList 3가지

1. Singly Linked List (단순 연결리스트)

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

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

LinkedList 기본구조

여러 개 Node가 포인터를 이용하여 하나로 연결되어 있는 데이터 구조입니다.

Node

1. Data : 데이터 요소

2. Next : 다음 노드 포인터

시간복잡도

항목	Arrays	LinkedList
삽입/삭제	O(n)	O(1)
탐색	O(1)	O(n)
메모리 사용	O	X

요약

LinkedList의 노드 삽입과 삭제는 정확한 위치를 알고 있다면 O(1) 시간으로 상대적으로 빠릅니다.
삽입과 삭제 위치의 탐색이 필요한 경우 O(n) 시간이 소요됩니다.

LinkedList는 하나의 데이터에 접근하는 경우 n번 만큼 이동시간이 발생하여 상대적으로 느립니다.

LinkedList의 노드는 다음 데이터의 주소를 갖고 있어 메모리 공간을 차지하지 않습니다.