2025-08-11 TIL

📕오늘의 공부 주제

---

LinkedList의 특성과 동작 원리

🤔Why?

---

구현이나 특성 차이를 잘 몰랐다는 걸 깨닫고 이번 기회에 확실히 정리하려고 합니다. 특히 **ArrayList**나 **배열**과 비교해서 장단점을 이해하면, 자료구조 선택이 훨씬 명확해집니다.

📖오늘의 공부 내용

---

1. LinkedList란?

• 데이터를 노드(Node) 단위로 저장하는 자료구조.
• 각 노드는 데이터 값과 다음 노드(Next) 참조를 가짐.
• 필요에 따라 이전 노드(Prev) 참조를 가지면 이중 연결 리스트(Double LinkedList).

---

2. LinkedList 구조

'''text
[Data|Next] -> [Data|Next] -> [Data|Next] -> null
'''

• 첫 번째 노드: Head
• 마지막 노드: Tail (Next가 null)

---

3. 특징

1. 메모리 연속성 불필요
   • 배열과 달리 메모리가 연속적으로 할당되지 않아도 됨.
2. 삽입/삭제 효율
   • 노드 참조만 변경하면 되므로 O(1) (단, 해당 위치를 찾는 데 O(n))
3. 탐색 속도
   • 인덱스 기반 접근 불가 → 처음부터 순차적으로 탐색(O(n))
4. 메모리 사용
   • 데이터 외에 Next(Prev) 참조까지 저장하므로 추가 메모리 사용.

---

4. ArrayList와 비교

구분	ArrayList	LinkedList
메모리	연속적	비연속적
접근 속도	O(1) (인덱스)	O(n)
삽입/삭제	중간 삽입 시 O(n)	위치만 알면 O(1)
캐시 효율	높음	낮음

---

5. C# LinkedList 예시

'''csharp
LinkedList list = new LinkedList();

// 추가
list.AddLast(1);
list.AddLast(2);
list.AddFirst(0);

// 탐색
foreach (var item in list)
{
Console.WriteLine(item);
}

// 삭제
list.Remove(1);
'''

---

6. 결론

• 장점: 삽입/삭제가 빠르고 메모리 재할당이 필요 없음.
• 단점: 탐색 속도 느림, 추가 메모리 사용.
• ✅ 정리: 데이터 추가/삭제가 잦고, 순차 접근이 주로 필요할 때 적합.