[Data Structure] 5. 연결 리스트 (Linked List)

연결리스트란

전 글에서 배열과 배열을 기반으로 한 List에 대해서 작성했습니다.
연결 리스트(Linked List)는 리스트와 이름은 비슷하지만 다른 원리로 만든 자료구조입니다.
Linked List, 말 그대로 요소(노드)들의 연결(Link)로 이루어진 자료구조입니다.

연결리스트의 구조

리스트는 데이터들이 연속적으로 메모리에 할당됩니다. 하지만 연결리스트는 데이터들이 불연속적으로 메모리에 할당되어있습니다.
연결리스트에서 데이터들은 노드(Node - 마디)라고 부릅니다.
각 노드들은 자신의 데이터와 다음 노드로 가리키는 주소(방향)을 가지고 있습니다. 이를 통해 데이터가 불연속적으로 메모리에 할당 되어있지만 이전/다음 노드로 넘어갈 수 있게 됩니다.

• 연결리스트 노드 클래스

public class LinkedListNode<T>
{
	internal LinkedList<T> list;
	internal LinkedListNode<T> prev;	// 이전 노드
	internal LinkedListNode<T> next;	// 다음 노드
	private T item;

	public LinkedListNode(T value)
	{
		this.list = null;
		this.prev = null;
		this.next = null;
		this.item = value;
	}

	public LinkedListNode(LinkedList<T> list, T value)
	{
		this.list = list;
		this.prev = null;
		this.next = null;
		this.item = value;
	}

	public LinkedListNode(LinkedList<T> list, LinkedListNode<T> prev, LinkedListNode<T> next, T value)
	{
		this.list = list;
		this.prev = prev;
		this.next = next;
		this.item = value;
	}

	public LinkedList<T> List { get { return list; } }
	public LinkedListNode<T> Prev { get { return prev; } }
	public LinkedListNode<T> Next { get { return next; } }

	public T Item { get { return item; } set { item = value; } }
}

• 연결리스트 클래스

  연결리스트 클래스에선 가장 처음 데이터(노드)를 head / first 라고 하며 가장 마지막 데이터를 tail / last 라고 합니다.
  그리고 배열과 다르게 Length가 아니라 Count를 통해 크기를 반환합니다.

단일 연결 리스트 : 노드가 다음 링크로만 연결되어 있음
이중 연결 리스트 : 노드가 이전 노드, 다음 노드 모두 연결되어 있음
순환 연결 리스트 : 마지막 노드가 다음 노드로 처음 노드를 가리키고 있음

public class LinkedList<T>
	{
		private LinkedListNode<T> head;	// 가장 처음 노드
		private LinkedListNode<T> tail; // 가장 마지막 노드
		private int count;	// 연결리스트 데이터의 갯수

		public LinkedList()	// 생성자
		{
			this.head = null;	// 처음엔 데이터가 없으니 null
			this.tail = null;
			count = 0;
		}

		public LinkedListNode<T> First { get { return head; } }
		public LinkedListNode<T> Last { get { return tail; } }
		public int Count { get { return count; } }
        

연결리스트의 접근/탐색

리스트는 데이터가 연속적으로 메모리에 할당되어 있어 Index를 사용할 수 있었습니다. Index를 사용해 접근과 탐색에서 O(1)의 시간복잡도를 가져 접근과 탐색에 유리한 반면, 연결리스트는 Index를 사용할 수 없어 접근과 탐색에서 O(N)의 불리한 시간복잡도를 가지고 있습니다.

연결리스트의 접근

public LinkedListNode<T> Find(T value)
	{
	LinkedListNode<T>? node = head;
	EqualityComparer<T> c = EqualityComparer<T>.Default;
	if (value != null)
	{
		while (node != null)
		{
			if (c.Equals(node.Item, value))
					return node;
			else
				node = node.next;
			}
		}
		else
		{
			while (node != null)
			{
				if (node.Item == null)
					return node;
				else
					node = node.next;
			}
		}
		return null;
	}
}

연결리스트의 탐색

연결리스트의 삽입/삭제

접근과 탐색에서는 O(N)의 시간 복잡도를 가진 연결리스트이지만 연결리스트에서 삽입과 삭제는 리스트에 비해 유리한 시간 복잡도를 가지게 됩니다.

연결리스트의 삽입

연결리스트에서 데이터를 삽입할 때 먼저 새로운 LinkedListNode를 만듭니다. 그 이후 삽입할 데이터의 이전과 이후 데이터에서 가리키는 방향을 그 데이터로 바꾸면 됩니다.

// 링크드리스트 요소 삽입 AddBefore, AddAfter
	public LinkedListNode<T> AddBefore(LinkedListNode<T> node, T value)
	{
		ValidateNode(node);
		LinkedListNode<T> newNode = new LinkedListNode<T>(this, alue);
		InsertNodeBefore(node, newNode);
		if (node == head)
			head = newNode;
		return newNode;
	}
    
	public LinkedListNode<T> AddAfter(LinkedListNode<T> node, T value)
	{
		ValidateNode(node);
		LinkedListNode<T> newNode = new LinkedListNode<T>(this, value);
		InsertNodeAfter(node, newNode);
		if (node == tail)
			tail = newNode;
		return newNode;
	}
   
// Linked List 노드를 통한 요소 삽입
	public LinkedListNode<T> AddFirst(T value)
	{
		LinkedListNode<T> newNode = new LinkedListNode<T>(this, value);
		if (head != null)
		{
			InsertNodeBefore(head, newNode);
			head = newNode;
		}
		else
		{
			InsertNodeToEmptyList(newNode);
		}
		return newNode;
	}

	public LinkedListNode<T> AddLast(T value)
	{
		LinkedListNode<T> newNode = new LinkedListNode<T>(this, value);
		if (tail != null)
		{
			InsertNodeAfter(tail, newNode);
			tail = newNode;
		}
		else
		{
			InsertNodeToEmptyList(newNode);
		}
		return newNode;
	}

연결리스트의 삭제

연결리스트에서 데이터를 삭제할 때 방법 자체는 간단합니다.
A -> B -> C 의 순서로 LinkedList가 구현되어 있을 때 B를 제거하고 싶다면 A -> B 를 A -> C 로 변경하면 됩니다. 그림으로 표현하면 이렇습니다.

C# 에서의 연결리스트

가리키는 방향을 변경한 후 메모리를 free 시키면 제거 됩니다. 이 때 C# 은 직접 메모리의 할당을 풀어주지 않아도 GC(가비지 컬렉터)가 메모리를 제거해줍니다. 그래서 연결리스트의 참조값만 변경하면 됩니다.
하지만 GC의 잦은 발생은 많은 메모리의 발생과 게임에서 프레임 드랍을 유발할 수 있습니다. 그래서 GC의 사용을 최소화하는게 GC의 효율을 높일 수 있는 방법입니다. 그래서 C#에서 노드기반의 연결리스트는 GC 발생을 유발할 수 있어 사용을 지양하는 것이 좋습니다.

틀린 내용이나 추가 의견 주시면 감사합니다