[자료구조] 링크드 리스트

🎻 링크드 리스트

링크드 리스트: 노드를 연결시킨 자료구조

• 데이터를 갖고 있는 데이터의 묶음

장점

• 길이가 가변적임 (배열의 단점 보완)
• 불필요하게 공간을 차지하지 않음 (배열의 단점 보완)

단점

• 노드 탐색시 시간 복잡도 문제

🎻 일반 배열 vs. 링크드 리스트

메모리 공간

• 배열: 연속된 메모리 공간에 존재
• 링크드 리스트: 메모리 상 떨어져 있는 데이터들이 앞의 데이터와 뒤의 데이터를 기억하는 형태

탐색

• 배열: O(1)
• 링크드 리스트: 탐색 필요. O(N)

데이터 추가/삭제

• 배열: O(N)
• 링크드 리스트: O(1)

메모리 할당

• 배열: 컴파일 타임에 할당. 정적 메모리 할당 > stack 영역
• 링크드 리스트: 런타임에 할당. 동적 메모리 할당 > heap 영역

🎻 다른 자료구조

링크드 리스트로 스택, 큐를 포함한 다양한 자료구조를 구현할 수 있음

---

참고:

• [자료구조] Array와 Linked List의 차이는 무엇일까?