C# 자료구조 (이중 연결 리스트, 원형 연결 리스트)
전 페이지에서는 단일 연결 리스트를 설명했으니 이번엔 이중 연결 리스트를 설명과 코드를 적어보겠다.
이중 연결 리스트
각 노드가 이전의 노드와 다음 노드를 모두 가리키는 양방향 노드이다.
그림으로 보았듯이 첫번째 head를 기준으로 각 4개의 노드가 양방향으로 포인터가 가리켜져 있는걸 볼수있다.
이제 코드를 적어보겠다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LinkedList_양방향_연걸
{
public class DoublyLinkedListNode<T>
{
public T Data { get; set; }
public DoublyLinkedListNode<T> Prev { get; set; }
public DoublyLinkedListNode<T> Next { get; set; }
public DoublyLinkedListNode(T data) : this(data, null, null)
{
}
public DoublyLinkedListNode(T data, DoublyLinkedListNode<T> prev, DoublyLinkedListNode<T> next)
{
this.Data = data;
this.Prev = prev;
this.Next = next;
}
}
public class DoublyLinkedList<T>
{
private DoublyLinkedListNode<T> head;
public void Add(DoublyLinkedListNode<T> newNode)
{
// 리스트가 비어있으면
if (head == null)
{
head = newNode;
}
//비어 있지 않으면, 마지막으로 이동하여 추가
else
{
var current = head;
while (current != null && current.Next != null)
{
current = current.Next;
}
// 추가할 때 양방향 연결
current.Next = newNode;
newNode.Prev = current;
newNode.Next = null;
}
}
public void AddAfter(DoublyLinkedListNode<T> current, DoublyLinkedListNode<T> newNode)
{
if (head == null || current == null || newNode == null)
{
throw new InvalidOperationException();
}
newNode.Next = current.Next;
current.Next.Prev = newNode;
newNode.Prev = current;
current.Next = newNode;
}
public void Remove(DoublyLinkedListNode<T> removeNode)
{
if (head == null || removeNode == null)
{
return;
}
// 삭제 노드가 첫 노드이면
if (removeNode == head)
{
head = head.Next;
if(head != null)
{
head.Prev = null;
}
}
//첫 노드가 아니면, Prev노드와 Next노드를 연결
else
{
removeNode.Prev.Next = removeNode.Next;
if (removeNode.Next != null)
{
removeNode.Next.Prev = removeNode.Prev;
}
}
removeNode = null;
}
public DoublyLinkedListNode<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;
while (current != null)
{
cnt++;
current = current.Next;
}
return cnt;
}
}
class Program
{
static void Main(string[] args)
{
//정수형 이중 연결 리스트 생성
var list = new DoublyLinkedList<int>();
// 리스트에 0 ~ 4 추가
for (int i = 0; i < 5; i++)
{
list.Add(new DoublyLinkedListNode<int>(i));
}
// index가 2인 요소 삭제
var node = list.GetNode(2);
list.Remove(node);
// index가 1인 요소 가져오기
node = list.GetNode(1);
// index가 1인 요소 뒤에 100 삽입
list.AddAfter(node,
new DoublyLinkedListNode<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);
}
// 리스트 역으로 출력
// 결과 : 4 3 100 1 0
//node = list.GetNode(4);
for (int i = count - 1; i >= 0; i--)
{
var n = list.GetNode(i);
Console.WriteLine(n.Data);
//node = node.Prev;
}
}
}
}
일단 노드의 데이터를 저장하고 전 노드와 다음 노드를 연결시킬 DoublyLinkedListNode클래스를 만든다.
여기서 단일 연결 리스트의 노드를 관리하는 클래스와 차이점은 이전 노드를 가리키는 Prev파라미터를 만들고
this 생성자를 이용해서 node만 값을넣고 Next, Prev는 null값으로 지정
여기서 때에 따라 Next Prev에 마지막 노드를 연결할수 있는 원형 연결 리스트가 있는데 이건 좀 있다가 설명을 하고
이제 소개할것은 DoublyLinkedList클래스인데 Remove 메서드를 제와하고는 Prev 파라미터에 이전 인덱스에 있는 데이터를 할당하는거 빼고는 달라진게없다.
그래서 Remove메서드가 뭐가 달라졌는지 설명을 할것이다.
Remove메서드는 단일연결 리스트에는 Next밖에 없어서 시간 복잡도가 O(n)이였던걸 알수있다.
하지만 이중 연결 리스트에는 지금 데이터에 이전 데이터를 알수있어서 while문이나 for문을 이용해서
removeNode를 삭제할 전 데이터까지 안가도 되고 바로 removeNode의 Prev데이터와 removeNode의 Next데이터를 연결 시켜주기만 하면 된다.
이렇게되면 O(1)로 바로 처리를 할수있다.
하지만 아직도 Add부분은 O(n)의 시간복잡도를 가지고 있기때문에 이걸 또 상쇄시킬 원형 연결 리스트를 소개하겠다.
원형 연결 리스트
원형 연결 리스트는 형태는 이중 연결 리스트와 같지만 한가지 차이점은 마지막 노드와 첫번째 노드가 연결되어서 순환할수 있는게 차이점이다.
그림으로 보았듯이 이중 연결 리스트와 양방향의 포인터를 가리키는건 같지만 첫번째 노드와 마지막 노드가 연결 되어있는걸 볼수 있다.
원형 연결 리스트 코드는 다른 코드들과 좀 다를수 있는데 이건 내가 직접 만들어 본것으로 다른 것들은 코드를 따라하면서 이해를 한것이지만 이걸 활용해서 직접 만들어보았다.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace LinkdList_원형_연결
{
public class DoublyLinkedListNode<T>
{
public T Data { get; set; }
public DoublyLinkedListNode<T> Next { get; set; }
public DoublyLinkedListNode<T> Prve { get; set; }
public DoublyLinkedListNode(T node) : this(node , null, null)
{
}
DoublyLinkedListNode(T node, DoublyLinkedListNode<T> Next, DoublyLinkedListNode<T> Prev)
{
this.Data = node;
this.Next = Next;
this.Prve = Prev;
}
}
public class CircularLinkedList<T>
{
DoublyLinkedListNode<T> head = null;
int count = 0;
public void AddNode(DoublyLinkedListNode<T> newNode)
{
DoublyLinkedListNode<T> current;
//아직 리스트가 없을때
if (head == null)
{
head = newNode;
head.Next = head;
head.Prve = head;
count++;
}
else
{
var tail = head;
tail.Prve.Next = newNode;
newNode.Prve = tail.Prve;
newNode.Next = head;
head.Prve = newNode;
count++;
}
}
public void AddAfterNode(DoublyLinkedListNode<T> currentNode, DoublyLinkedListNode<T> newNode)
{
newNode.Next = currentNode.Next;
newNode.Prve = currentNode;
newNode.Next.Prve = newNode;
currentNode.Next = newNode;
count++;
}
public void RemoveNode(DoublyLinkedListNode<T> removeNode)
{
// 첫번째 리스트를 없앨때
if (head == removeNode)
{
head.Prve = head.Next.Prve;
head.Prve.Next = head.Next;
head = head.Next;
removeNode = null;
count--;
}
else
{
removeNode.Next.Prve = removeNode.Prve;
removeNode.Prve.Next = removeNode.Next;
removeNode = null;
count--;
}
}
public DoublyLinkedListNode<T> GetNode(int index)
{
DoublyLinkedListNode<T> current;
current = head;
for(int i = 0; i < index; i++)
{
current = current.Next;
}
return current;
}
public int Count()
{
return count;
}
}
class Program
{
static void Main(string[] args)
{
// 정수형 원형 연결 리스트 생성
var list = new CircularLinkedList<int>();
//리스트에 0 ~ 5 추가
for (int i = 0; i < 5; i++)
{
list.AddNode(new DoublyLinkedListNode<int>(i));
}
// Index가 2인 요소 삭제
var node = list.GetNode(2);
list.RemoveNode(node);
// Index가 1인 요소 가져오기
node = list.GetNode(1);
// index가 1인 요소 뒤에 100 삽입
list.AddAfterNode(node, new DoublyLinkedListNode<int>(100));
// 리스트 카운트 체크
int count = list.Count();
//원형 리스트 확인 위해 리스트 두배 출력
//결과 : 0 1 100 3 4 0 1 100 3 4
node = list.GetNode(0);
for (int i = 0; i <count * 2; i++)
{
Console.WriteLine(node.Data);
node = node.Next;
}
}
}
}
여기서는 Count메서드를 굳이 for문이나 while문으로 할 이유가 있나 싶어서 객체를 생성할때 count변수를 만들어서 추가하거나 삭제할때 ++, --를 하였고 Count 메서드에 바로 count변수를 리턴하도록 만들었다.
이건 이거고 여기서 이중 연결 리스트와 다른게 이제 Add메서드 라고 할수있다.
Add메서드는 head 데이터를 teil변수에다 포인터를 가리키게하고 tail.Prev.Next에다 새로운 데이터 인자인 newNode를 넣고 newNode.Prev 파라미터에 teil.Prev를 데이터를 넣고 newNode.Next에는 head head.Prev에는 newNode를 넣으면 완성이된다.
단일과 이중 연결 리스트는 순환이 불가능해서 while, for문을 이용해 마지막 노드까지 가야하므로 시간 복잡도가 O(n)이였지만
원형 연결 리스트는 순환이 가능하기에 바로 마지막노드를 가리키는 head.Prev 파라미터가 존재해 바로 연결이 가능하므로 시간 복잡도는 O(1)이 된다.
이렇게보니 teil변수를 head.Prev 파라미터를 할당하게하면 더 깔끔한 코드를 만들수 있었을것같다.