C# 연결리스트(Linked List)에 대해 알아보자!

연결리스트(Linked List)란?

 

• 연결리스트는 일반 리스트처럼 순차적으로 데이터를 추가/삭제할 수도 있고, 원하는 위치의 데이터를 추가/삭제할 수 있습니다.
• 이 연결된 구조체는 메모리 상에서 물리적으로 연속된 영역에 저장되지 않고, 각 노드가 개별적으로 할당되어 다음 노드를 가리키는 포인터를 이용하여 연결합니다.
• 하지만 인덱스를 통해 직접 접근하는 데는 제약이 있고, 탐색 연산의 비용이 높아 데이터의 삽입과 삭제가 빈번한 경우에 유용하게 사용됩니다.
  
  
• 여기서 노드란, 연결리스트나 트리 등과 같은 자료구조에서 기본적인 데이터 단위입니다. 각 노드는 두 가지 주요 요소로 구성됩니다.
  1. 데이터(값): 노드가 저장하는 실제 정보입니다. 이 데이터는 정수, 문자열 등 어떤 형식이든 될 수 있습니다.
  2. 링크: 다음 노드를 가리키는 참조입니다. 이 링크를 통해 연결 리스트나 트리에서 다음 노드로 이동할 수 있습니다. 만약 마지막 노드라면 링크는 보통 null 또는 특정 종료 값을 가집니다.

<출처: https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FH3aKU%2FbtroXMwroIq%2FXkInYOTuNQtrjDLdz27uH0%2Fimg.png>

 

• 단순 연결 리스트
  - 각 노드가 다음 노드를 가리키는 링크만을 갖습니다.
  - 각 노드에서 다음 노드로만 이동 가능합니다.
  
  
• 이중 연결 리스트
  - 각 노드가 이전 노드와 다음 노드를 가리키는 두 개의 링크를 갖습니다.
  - 양쪽 방향으로 이동 및 탐색이 가능합니다.
  - 단순 연결 리스트에 비해 두 개의 링크를 저장해야 하므로 메모리 사용량이 더 많지만, 양 방향으로 이동 및 탐색이  가능한 장점이 있습니다.
  
  
• 원형 연결 리스트
  - 마지막 노드가 첫 번째 노드를 가리키는 링크를 갖습니다. 꼬리와 머리가 연결된 원형 구조를 이루게 됩니다.
  - 마지막 노드의 다음 링크가 첫 번째 노드입니다. 이로 인해 마지막 노드에서 첫 번째 노드로 이동이 가능하게 됩니다.

<출처: https://blog.kakaocdn.net/dn/ba3zRZ/btq2Mz8CDoL/wNmI6SzXTZhPko7X7zBALK/img.png>

---

연결리스트(LinkedList)를 사용해보자!

 

1. 노드 추가

1) AddFirst(T value) - 맨 앞에 새 노드 추가

2) AddLast(T value) - 맨 뒤에 새 노드 추가

3) AddBefore(T node, T value) - 특정 노드 앞에 value추가

4) AddAfter(T node , T value) - 특정 node값 뒤에 value추가

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

linkedList.AddLast(20);
linkedList.AddLast(30);
linkedList.AddFirst(10);

LinkedListNode<int> node = linkedList.Find(20);

linkedList.AddBefore(node, 15);
linkedList.AddAfter(node, 25);

foreach (var item in linkedList)
{
	Debug.Log(item);
}

 

2. 노드 제거

1) Remove(T value) - 특정 값이 있는 노드 제거

2) RemoveFirst() -  맨 앞 노드 제거

3) RemoveLast() - 맨 뒤 노드 제거

4) Clear() - 모두 제거

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

linkedList.AddLast(20);
linkedList.AddLast(30);
linkedList.AddFirst(10);

LinkedListNode<int> node = linkedList.Find(20);

linkedList.AddBefore(node, 15);
linkedList.AddAfter(node, 25);

linkedList.Remove(20); //20이 들어있는 노드 제거.
linkedList.RemoveFirst(); //첫번째 노드 제거.
linkedList.RemoveLast(); //마지막 노드 제거.

foreach (var item in linkedList)
{
	Debug.Log(item);
}

 

3. 노드 개수 및 탐색

1) Count - 해당 연결리스트의 노드 개수

2) Contain() - 해당 값이 있는 노드가 포함되어있는지 여부 확인. bool값을 리턴.

3) Find() - 해당 값이 있는지 찾고 있으면 해당 값을 리턴, 아니면 null입니다.

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

linkedList.AddLast(20);
linkedList.AddLast(30);
linkedList.AddFirst(10);

LinkedListNode<int> node = linkedList.Find(20);

//linkedList의 노드 개수를 출력.
Debug.Log(linkedList.Count);

//linkedList에 100이라는 값이 있는 노드가 있으면 true, 없으면 false.
Debug.Log(linkedList.Contains(100));

//linkedList에 20이라는 값이 있는 노드가 있으면 그 값을 node에 전달.
Debug.Log(node.Value);

---