3.1 연결 리스트의 기초개념
연결리스트(Linked List)는 각 노드가 데이터와 포인터를 가지고 있으면서 노드들이 한 줄로 쭉 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 노드들이 한 방향으로 각 노드가 다음 노드를 가리키고 있는 리스트를 단일 연결 리스트(Singly Linked List)라 하고, 각 노드가 이전 노드와 다음 노드를 모두 가리키는 양방향 노드로 되어 있는 것을 이중 연결 리스트(Doubly Linked List)라 한다.
3.2 단일 연결 리스트
단일 연결 리스트(Singly Linked List)는 단방향으로 노드들을 연결한 간단한 자료구조이다. 아래는 4개의 노드를 갖는 단일 연결 리스트를 표현한 예이다.
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; // 리스트의 첫 노드를 가리키는 헤드 필드, 이 Head로 전체 리스트를 순차적으로 엑세스함
/// <summary>
/// 새 노드를 추가하는 메서드
/// </summary>
/// <param name="newNode"></param>
public void Add(SinglyLinkedListNode<T> newNode)
{
// 리스트가 비어있으면
if (head == null)
{
head = newNode;
}
else // 비어 있지 않으면,
{
var current = head;
// 마지막 노드로 이동하여 추가
while (current != null & current.Next != null)
{
current = current.Next;
}
current.Next = newNode;
}
}
/// <summary>
/// 새 노드를 중간에 삽입하는 메서드
/// </summary>
/// <param name="current"></param>
/// <param name="newNode"></param>
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;
}
/// <summary>
/// 특정 노드를 지우는 메서드
/// </summary>
/// <param name="removeNode"></param>
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;
}
}
}
/// <summary>
/// 지정한 위치에 있는 노드를 반환하는 메서드
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
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;
}
/// <summary>
/// Head부터 마지막 노드까지 이동하면서 카운트를 증가시키는 메서드
/// </summary>
/// <returns></returns>
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 SinglyLinkedList<int>();
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);
// Index가 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);
}
}
}3.3 이중 연결 리스트
이중 연결 리스트(Doubly Linked List)는 단방향으로 연결된 단일 연결 리스트의 탐색 기능을 개선한 것으로서 리스트안의 노드가 이전 노드와 다음 노드를 가리키는 포인터를 모두 가지고 있어서 양방향으로 탐색이 가능한 자료 구조이다.
예를 들어, 아래 그림은 4개의 노드를 갖는 이중 연결 리스트를 표현한 예이다.
public class DoublyLinkedListNode<T>
{
public T Data
{
get; set;
}
public DoublyLinkedListNode<T> Next
{
get; set;
}
public DoublyLinkedListNode<T> Prev
{
get; set;
}
public DoublyLinkedListNode(T data)
{
this.Data = data;
this.Next = null;
}
}
public class DoublyLinkedList<T>
{
private DoublyLinkedListNode<T> head; // head
/// <summary>
/// 리스트가 비어 있으면 Head에 새 노트를 할당하고, 비어 있지 않으면 마지막 노드를 찾아 이동한 후
/// 마지막 노드 다음에 새 노드를 추가한다.
/// </summary>
/// <param name="newNode"></param>
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;
}
}
/// <summary>
/// 현재 노드(currNode)를 A, 새로 추가하는 노드를 B, 현재 노드의 다음 노드를 C라고 가정
/// A의 Next 레퍼런스를 B에 연결하고, C의 Prev 레퍼런스를 B에 연결하고, B의 Prev를 A에,
/// B의 Next를 C에 연결함
/// </summary>
/// <param name="current"></param>
/// <param name="newNode"></param>
/// <exception cref="InvalidOperationException"></exception>
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;
}
/// <summary>
/// 삭제할 노드가 첫 노드이면, Head의 다음노드 즉 두번째 노드를 Head에 할당하고,
/// 첫 노드가 아니면 삭제할 노드의 이전 노드와 다음 노드를 서로 연결한다.
/// </summary>
/// <param name="removeNode"></param>
public void Remove(DoublyLinkedListNode<T> removeNode)
{
if(head == null || removeNode == null)
{
return;
}
// 삭제 노드가 첫 노드이면
if (removeNode == null)
{
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;
}
/// <summary>
/// 이중 연결 리스트에서 특정 위치 인덱스에 있는 노드를 리턴한다.
/// 만약 인덱스가 리스트 밖에 있으면, null을 리턴한다.
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public DoublyLinkedListNode<T> GetNode(int index)
{
var current = head;
for(int i = 0; i <index && current != null; i++)
{
current = current.Next;
}
return current;
}
/// <summary>
/// Head부터 마지막 노드까지 이동하면서 카운트를 증가시킴
/// </summary>
/// <returns></returns>
public int Count()
{
int cnt = 0;
var current = head;
while(current != null)
{
cnt++;
current = current.Next;
}
return cnt;
}
}
/// <summary>
/// 이중 연결 리스트에 0,1,2,3,4 요소를 추가하고 중간의 2를 삭제하고
/// 대신 100을 넣은 후, 전체 리스트를 순방향과 역방향으로 출력하는 것임.
/// </summary>
class Program
{
static void Main(string[] args)
{
// 정수형 이중 연결 리스트 생성
var list = new DoublyLinkedList<int>();
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 = 0; i < count; i++)
{
Console.WriteLine(node.Data);
node = node.Prev;
}
}
}3.4 원형 연결 리스트
원형 연결 리스트(Circular Linked List)는 환형 연결 리스트라고도 하는데, 일반 연결 리스트에서 마지막 노드를 처음 노드에 연결시켜 원형으로 만든 구조이다. 원형 연결 리스트를 단방향으로 연결한 것을 원형 단일 연결 리스트(Singly Circular Linked List)라 하고, 양방향으로 연결한 것을 원형 이중 연결 리스트(Doubly Circular Linked List)라 한다. 아래 그림은 4개의 노드를 갖는 원형 이중 연결 리스트를 표현한 예이다. 첫 노드의 이전(Prev)노드는 마지막 노드를 가리키고, 마지막 노드의 다음(Next)노드는 첫 노드를 가리키고 있다.
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 DoublyLinkedListNode<T>
{
public T Data
{
get; set;
}
public DoublyLinkedListNode<T> Next
{
get; set;
}
public DoublyLinkedListNode<T> Prev
{
get; set;
}
public DoublyLinkedListNode(T data)
{
this.Data = data;
this.Next = null;
}
}
class CircularLinkedList<T>
{
private DoublyLinkedListNode<T> head;
/// <summary>
/// 리스트가 비어있으면 Head에 새 노드를 할당
/// 비어있지 않으면 첫 노드의 이전노드인 마지막 노드를 찾음
/// 첫 노드와 마지막 노드 사이에 새 노드를 추가함.
/// 마지막 노드를 찾기 위해 모든 노드를 순차적으로 이동할 필요가 없음
/// 첫 노드의 이전노드가 항상 마지막 노드를 가리키므로 바로 마지막 노드를 알아 낼 수 있기 때문임
/// </summary>
/// <param name="newNode"></param>
public void Add(DoublyLinkedListNode<T> newNode)
{
if (head == null) // 리스트가 비어있으면
{
head = newNode;
head.Next = head;
head.Prev = head;
}
else
{
var tail = head.Prev;
head.Prev = newNode;
tail.Next = newNode;
newNode.Prev = tail;
newNode.Next = head;
}
}
/// <summary>
/// 이중 연결 리스트와 동일한 메소드임
/// 단, 이중연결리스트는 마지막 노드 다음이 null이어서 current.Next.prev 문장에 대해 current.Next가 null인지 먼저 체크해야 하지만,
/// 원형 이중 연결 리스트는 마지막 노드 다음이 헤드이므로 별도로 null을 체크할 필요가 없다.
/// </summary>
/// <param name="current"></param>
/// <param name="newNode"></param>
/// <exception cref="InvalidOperationException"></exception>
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 = newNode;
newNode.Prev = current;
current.Next = newNode;
}
/// <summary>
/// 삭제할 노드가 첫 노드이고 전체 노드의 수가 하나이면, 헤드를 null로 설정함
/// 이 경우가 아니면, 삭제할 노드의 이전 노드와 다음 노드를 서로 연결하는 작업을 진행하고, 삭제할 노드를 null로 설정함
/// </summary>
/// <param name="removeNode"></param>
public void Remove(DoublyLinkedListNode<T> removeNode)
{
if(head == null || removeNode == null)
{
return;
}
if(removeNode == head && head == head.Next)
{
head = null;
}
else // 아니면 Prev 노드와 Next 노드를 연결
{
removeNode.Prev.Next = removeNode.Next;
removeNode.Next.Prev = removeNode.Prev;
}
removeNode = null;
}
/// <summary>
/// 이중 연결 리스트에서 특정 위치 인덱스에 있는 노드를 리턴한다. 리스트가 원형이므로 루프를 돌며
/// 이동할 때 다시 순환해서 헤드로 돌아오면 찾는 노드가 없는 것이므로 null을 리턴함
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public DoublyLinkedListNode<T> GetNode(int index)
{
if (head == null) return null;
int cnt = 0;
var current = head;
while(cnt < index)
{
current = current.Next;
cnt++;
if(current == head)
{
return null;
}
}
return current;
}
/// <summary>
/// Head부터 마지막 노드까지 이동하면서 카운트를 증가시킴
/// 마지막 노드의 다음 노드로 이동하면 Head를 만나게 되므로 이러한 조건일 때 루프를 중지하면 된다
/// </summary>
/// <returns></returns>
public int Count()
{
if (head == null) return 0;
int cnt = 0;
var current = head;
do
{
cnt++;
current = current.Next;
} while (current != head);
return cnt;
}
/// <summary>
/// 원형 연결 리스트인지 체크
/// 리스트가 원형인지 아닌지를 판별하는 코드
/// 기본적으로 Head로부터 출발하여 계속 다음노드를 따라가면서 다시 Head로 돌아오면 원형 연결 리스트
/// 마지막에 Null을 만나면 원형 연결 리스트가 아님
/// 연결리스트가 빈 리스트(Empty List)면, 원형 연결 리스트로 정의
/// </summary>
/// <param name="head"></param>
/// <returns></returns>
public static bool IsCircular(DoublyLinkedListNode<T> head)
{
// 빈 리스트는 원형 리스트임
if (head == null) return true;
var current = head;
while(current != null)
{
current = current.Next;
if(current == head)
{
return true;
}
}
return false;
}
public static bool IsCyclic(SinglyLinkedListNode<int> head)
{
var p1 = head;
var p2 = head;
do
{
p1 = p1.Next;
p2 = p2.Next;
if (p1 == null || p2 == null || p2.Next == null)
{
return false;
}
p2 = p2.Next;
} while (p1 != p2);
return true;
}
}
/// <summary>
/// 원형 연결 리스트에 0,1,2,3,4 요소를 추가하고 중간의 2를 삭제하고 대신 100을 넣음
/// 전체 리스트를 두번 출력해봄
/// 리스트가 원형이므로 전체 리스트 카운트의 2배 만큼 계속 이동하면 리스트를 두번 출력하게 된다
/// </summary>
class Program
{
static void Main(string[] args)
{
// 정수형 원형 연결 리스트 생성
var list = new CircularLinkedList<int>();
// 리스트에 0 ~ 5 추가
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 0 1 100 3 4
node = list.GetNode(0);
for(int i = 0; i< count * 2; i++)
{
Console.WriteLine(node.Data);
node = node.Next;
}
}
}3.5 원형 단일 연결 리스트의 변형
C#의 창시자로서 C#의 아버지라고도 불리우는 앤더스 헤일즈버그는 자신이 좋아하는 자료구조를 인터뷰에서 소개한 적이 있는데, 그것은 Head가 마지막 노드를 가리키는 원형 단일 연결 리스트이다.
이 리스트의 장점
1. 새 노드를 추가할 때 바로 Head 뒤에 노드를 즉시 추가할 수 있다.
2. 노드를 검색할 때는 Head의 다음 노드인 첫 노드로 이동하여 바로 일반 연결 리스트처럼 검색할 수 있다.
3. 원형 이중 연결 리스트가 2개의 링크를 계속 관리해야 하는 반면, 이 리스트는 하나의 링크만 관리하고도 O(1)의 성능으로 즉시 새로운 노드를 추가할 수 있다.
3.6 .NET의 연결 리스트
.NET에는 연결 리스트를 지원하는 클래스로 LinkedList가 있다. 이 LinkedList 클래스는 이중 연결 리스트(Doubly Linked List)로 구현되어 있으며, 리스트 노드는 LinkedListNode 클래스를 사용한다.
LinkedList는 개발자가 임의의 타입(T)을 지정할 수 있는 Generic 타입의 이중 연결 리스트이다. 이 LinkedList 클래스는 여러 메서드들을 제공하는데, 예를 들어 노드를 추가하기 위한 메서드로서 AddFirst, AddLast, AddBefore, AddAfter 등의 다양한 메서드가 있어 처음 또는 끝, 혹은 특정 노드의 앞, 뒤에 새 노드를 추가할 수 있다.
아래 코드는 LinkedList에 몇 개의 노드를 추가하고 검색, 출력해 보는 예제이다.
코드를 입력하세요
나는 코딩을 잘 하고 시파.