LinkedList

• LinkedList는 데이터를 노드 단위로 저장하는 자료구조다.

• 배열과 달리, 데이터가 메모리에 연속적으로 배치되지 않고 노드 간의 참조로 연결되어 있다.

• 노드는 값이 추가된 순서대로 자신의 앞과 뒤의 주소값을 가지고 있다.
  ex) 사슬처럼 연결

---

문법

LinkedList<int> linkedList = new LinkedList<int>();	// LinkedList
LinkedListNode<int> node;							// Node

---

특징

• 데이터의 삽입 및 삭제가 빠르다. (O(1))

• 연속적인 인덱스가 없어서 특정 위치의 데이터를 찾는 데 시간이 걸린다. (O(n))

• 배열과 다르게, 크기를 미리 할당할 필요가 없다.

종류

• 단일 연결 리스트 : 1 → 2 → 3 → ...

• 이중 연결 리스트 : 1 ↔ 2 ↔ 3 ↔ ...

• 원형 연결 리스트 : 1 → 2 → 3 → 1 → ...

• 원형 이중 연결 리스트 : 1 ↔ 2 ↔ 3 ↔ 1 ↔ ...

---

배열(Array)과의 차이점

비교	LinkedList	Array
메모리 배치	비연속적 (노드 연결)	연속적
접근	O(n)	O(1)
삽입	O(1)	O(n)
삭제	O(1)	O(n)
검색	O(n)	O(n)

---

예시

노드 추가

LinkedList<int> linkedList = new LinkedList<int>();
LinkedListNode<int> node;

node = linkedList.AddFirst(1);  // 첫 번째 위치에 추가
linkedList.AddLast(2);          // 마지막 위치에 추가
linkedList.AddAfter(node, 30);  // 특정 노드(node) 뒤에 추가
linkedList.AddAfter(node, 23);
linkedList.AddAfter(node, 12);
linkedList.AddAfter(node, 45);
// 1, 45, 12, 23, 30, 2

---

노드 삭제

linkedList.Remove(node);      // 특정 노드 삭제 (O(1))
linkedList.Remove(30);        // 특정 값 삭제 (O(n))
linkedList.RemoveFirst();     // 첫 번째 노드 삭제 (O(1))
linkedList.RemoveLast();      // 마지막 노드 삭제 (O(1))

---

순회 (탐색)

// for문을 이용한 순회
for (node = linkedList.First; node != null; node = node.Next)
{
    Console.WriteLine(node.Value);
}

// foreach문을 이용한 순회
foreach (var item in linkedList)
{
    Console.WriteLine(item);
}

---

노드 접근

LinkedListNode<int> firstNode = linkedList.First;  // 첫 번째 노드
LinkedListNode<int> lastNode = linkedList.Last;    // 마지막 노드

LinkedListNode<int> prevNode = node.Previous;  // 이전 노드
LinkedListNode<int> nextNode = node.Next;      // 다음 노드

---

값이 있는지 체크

bool exists = linkedList.Contains(12);  // 값이 존재하면 true 반환

---

노드와 노드가 연결되어 있는걸 보니,

Key 없이 Value만 있는 자료구조 같은 느낌이다.