C# 자료구조 (단일 연결 리스트)
연결 리스트(Linked List)
연결 리스트란 각 노드가 데이터와 포인터를 가지고 있으면서 노드들이 한 줄로 쭉 연결되어 있는 데이터(객체)를 저장하는 자료구조 이다.
리스트를 만들라면 단일 연결 리스트, 이중 연결 리스트 , 원형 연결 리스트 등등이 있을수 있는데 일단 단일 연결 리스트를
설명하겠다.
단일 연결 리스트
단일 연결 리스트란 노드들이 한 방향으로 각 노드가 다음 노드를 가리키는 구조라고 할수있다.
이 그림은 첫번째 노드의 Head를 두고 4개의 노드가 단 방향으로 이어지는 구조이다.
이제 단일 연결 리스트를 만들 코드를 보여주겠다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LinkedList_단일연결
{
public class SinglyLinkedListNode<T>
{
public T Data { get; set; }
public SinglyLinkedListNode<T> Next { get; set; }
public SinglyLinkedListNode(T data)
{
this.Data = data;
this.Next = null;
}
}
public class SinglyLinkedList<T>
{
private SinglyLinkedListNode<T> head;
public void Add(SinglyLinkedListNode<T> newNode)
{
// 리스트가 비어 있으면
if (head == null)
{
head = newNode;
}
// 비어 있지 않다면
else
{
var cuurnet = head;
// 마지막 노드로 이동하여 추가
while (cuurnet != null && cuurnet.Next != null)
{
cuurnet = cuurnet.Next;
}
cuurnet.Next = newNode;
}
}
public void AddAfter(SinglyLinkedListNode<T> current,
SinglyLinkedListNode<T> newNode)
{
if (head == null || current == null || newNode == null)
{
throw new InvalidOperationException();
}
newNode.Next = current.Next;
current.Next = newNode;
}
public void Remove(SinglyLinkedListNode<T> removeNode)
{
if (head == null || removeNode == null)
{
return;
}
// 삭제할 노드가 첫 노드이면
if (removeNode == head)
{
head = head.Next;
removeNode = null;
}
// 첫노드가 아니면, 해당 노드를 검색하여 삭제
else
{
var current = head;
// 단반향이므로 삭제할 노드의
// 바로 이전 노드를 검색해야
while (current != null && current.Next != removeNode)
{
current = current.Next;
}
if (current != null)
{
//이전 노드의 Next에 삭제노드의 Next를 할당
current.Next = removeNode.Next;
removeNode = null;
}
}
}
public SinglyLinkedListNode<T> GetNode(int index)
{
var current = head;
for (int i = 0; i < index && current != null; i++)
{
current = current.Next;
}
//만약 index가 리스트 카운트보다 크면
//null이 리턴됨
return current;
}
public int Count()
{
int cnt = 0;
var current = head;
for (int i = 0; current != null; i++)
{
cnt++;
current = current.Next;
}
return cnt;
}
}
class Program
{
static void Main(string[] args)
{
var list = new SinglyLinkedList<int>();
// 리스트에 0 ~ 4 추가
for (int i = 0; i < 5; i++)
{
list.Add(new SinglyLinkedListNode<int>(i));
}
// index가 2인 요소 삭제
var node = list.GetNode(2);
list.Remove(node);
// index가 1인 요소 가져오기
node = list.GetNode(1);
// inex가 1인 요소 뒤에 100 삽입
list.AddAfter(node, new SinglyLinkedListNode<int>(100));
// 리스트 카운트 체크
int count = list.Count();
// 전체 리스트 출력
// 결과: 0 1 100 3 4
for (int i = 0; i < count; i++)
{
var n = list.GetNode(i);
Console.WriteLine(n.Data);
}
}
}
}
리스트를 만들려면 좀 코드가 길수도 있다.
처음엔 노드 데이터가 들어있고 다음 노드를 연결 시키는 SinglyLinkedListNode클래스를 만들고
이제 다양한 기능들을 넣는 SinglyLinkedList 클래스를 만든다.
SinglyLinkedList에 있는 메서드들을 소개하겠다.
Add
리스트에 데이터를 추가시키는 메서드로 리스트가 비어있으면 첫번째 노드 head에다 연결을 시키고
비어 있지 않다면 새로운 객체 current에다 head 데이터를 할당하고 current와 currnet.Next가 null이
아닐때까지 마지막 노드까지 가고 마지막 노드 Next에다 새로 추가할 데이터를 할당한다.
AddAfter
만약 인덱스가 2인 객체 다음에 추가할 객체를 삽입하고싶을때 쓰는 메서드로
원래 노드의 currentNode 와 currentNode 의 다음 데이터에 할당하고 싶은 newNode를 인자를 가져와서
newNode.Next에 currentNode.Next에 있던 데이터를 할당하게 하고 currentNode.Next에 newNode데이터를 삽입한다.
Remove
몇번 인덱스에 데이터를 지울때 쓰는 메서드로 지우고 싶은 데이터 removeNode 인자를 넣어서 첫번째 노드 head와 removeNode 널인지 체크하고 삭제할 노드가 첫번째 데이터(head)면 head는 head.Next로 옮기고 removeNode를 널로 바꿔서 원래 head값의 포인터를 가리키지 않게한다.
지우고싶은 데이터가 첫번째 데이터(head)가 아닐때는 Add에서 사용했듯이 current데이터를만들어 head데이터를 할당한후 current.Next가 removeNode데이터가 같을때까지 while문으로 지우고싶은 노드 전까지 간다음에
current.Next를 removeNode.Next에 연결을하고 원래 데이터 removeNode를 널값으로 만들어 포인터를 없애버린다.
GetNode
이 메서드는 말그대로 인덱스를 넣으면 그 인덱스에 맞는 데이터를 가져오는 메서드이다.
인자값은 현재 불러올 인덱스를 넣고 for문을 돌려 index보다 클때랑 current가 널이 아닐때까지 current.Next를 할당해
인덱스값에 맞는 데이터를 리턴한다.
Count
이 메서드는 현재 리스트의 갯수를 리턴하는 메서드로 int형 cnt변수를 선언하고 current가 null이 아닐때까지 cnt변수를
1씩 증가 끝나면 cnt변수를 리턴하게된다.
단반향의 단점은 Add메서드와 RemoveAdd메서드를 끝에 있는 노드까지 가야하므로 시간 복잡도가 O(n) 되버리는 단점이 있다.
이걸 좀 상쇄시킨 이중 연결 리스트를 다음 페이지에 소개하겠다.