[C#] 연결 리스트(Linked List)란?

1. 연결 리스트(Linked List)란?

* 연결 리스트(Linked List) : 데이터를 저장하는 자료구조. 각 노드가 데이터와 포인터를 가지고 있으면서 노드들이 한 줄로 쭉 연결되어 있는 방식.

2. 단일 연결 리스트(Singly Linked List)

 : 단방향으로 노드들을 연결한 간단한 자료 구조.

(ex) 아래는 4개의 노드를 갖는 단일 연결 리스트를 그림으로 표현한 것.

using System;

public class LinkedList_Study<T>
{
    public T Data { get; set; }
    public LinkedList_Study<T> Next { get; set; }
    public LinkedList_Study(T data)
    {
        this.Data = data;
        this.Next = null;
    }

    private LinkedList_Study<T> head;

    public void Add(LinkedList_Study<T> newNode) // 새 노드를 추가.
    {
        if (head == null) head = newNode; //리스트가 비어 있을 때 head에 새 노드를 할당.
        else // 리스트가 비어있지 않을 때.
        {
            var current = head;
            while (current != null && current.Next != null)  // 마지막 노드(Tail)로 이동하여 추가.
                current = current.Next;
            current.Next = newNode;
        }
    }

    public void AddAfter(LinkedList_Study<T> current, LinkedList_Study<T> newNode) //새 노드를 중간에 삽입.
    {
        if (head == null || current == null || newNode == null)
            throw new InvalidOperationException();
        newNode.Next = current.Next;
        current.Next = newNode;
    }

    public void Remove(LinkedList_Study<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)
            {
                current.Next = removeNode.Next;
                removeNode = null;
            }
        }
    }

    public LinkedList_Study<T> GetNode(int index) // 지정한 위치에 있는 노드를 반환.
    {
        var current = head;
        for (int i = 0; i < index && current != null; i++)
        {
            current = current.Next;
        }
        return current;
    }

    public int Count() // head부터 마지막 노드까지 이동하면서 카운트 증가(노드가 몇개 있는지)
    {
        int cnt = 0;
        var current = head;
        while(current != null)
        {
            cnt++;
            current = current.Next;
        }
        return cnt;
    }
}

 

3. 이중 연결 리스트(Double Linked List)

: 이전 노드와 다음 노드를 가리키는 포인터를 모두 갖고 있어 양방향으로 탐색이 가능한 자료구조.

(ex) 아래 그림은 4개의 노드를 갖는 이중 연결 리스트를 표현한 것.

using System;

public class LinkedList_Study2<T> //이중 링크 리스트 구현
{
    public T Data { get; set; }
    public LinkedList_Study2<T> Prev { get; set; }
    public LinkedList_Study2<T> Next { get; set; }

    public LinkedList_Study2(T data, LinkedList_Study2<T> prev, LinkedList_Study2<T> next)
    {
        this.Data = data;
        this.Prev = prev;
        this.Next = next;
    }

    public LinkedList_Study2(T data) 
        : this(data, null, null) { }

    private LinkedList_Study2<T> head;

    public void Add(LinkedList_Study2<T> newNode) //새 노드 추가.
    {
        if (head == null) head = newNode; //리스트가 비어있으면 head에 새 노드 할당
        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(LinkedList_Study2<T> current, LinkedList_Study2<T> newNode) //새 노드를 중간에 삽입
    {
        if (head == null || current == null || newNode == null)
            throw new InvalidOperationException();
        newNode.Next = current.Next;
        current.Next.Prev = newNode;
        newNode.Prev = current;
        newNode.Next = newNode;
    }

    public void Remove(LinkedList_Study2<T> removeNode) //특정 노드 삭제
    {
        if (head == null || removeNode == null) return;
        if(removeNode == head)
        {
            head = head.Next;
            if (head != null) head.Prev = null;
        }
        else
        {
            removeNode.Prev.Next = removeNode.Next;
            if (removeNode.Next != null)
                removeNode.Next.Prev = removeNode.Prev;
        }
        removeNode = null;
    }

    public LinkedList_Study2<T> GetNode(int index) //지정한 위치의 노드 반환
    {
        var current = head;
        for (int i = 0; i < index && current != null; i++)
        {
            current = current.Next;
        }
        return current;
    }

    public int Count()
    {
        int cnt = 0;
        var current = head;
        while(current != null)
        {
            cnt++;
            current = current.Next;
        }
        return cnt;
    }
}

4. 원형 연결 리스트(Circular Linked List)

: 일반 연결 리스트에서 마지막 노드를 처음 노드에 연결시켜 만든 구조.

(ex) 아래 그림은 4개의 노드를 갖는 원형 이중 연결 리스트를 표현한 것.

using System;

public class LinkedList_Study3<T> //이중 링크 리스트 구현
{
    public T Data { get; set; }
    public LinkedList_Study3<T> Prev { get; set; }
    public LinkedList_Study3<T> Next { get; set; }

    public LinkedList_Study3(T data, LinkedList_Study3<T> prev, LinkedList_Study3<T> next)
    {
        this.Data = data;
        this.Prev = prev;
        this.Next = next;
    }
    private LinkedList_Study3<T> head;

    public void Add(LinkedList_Study3<T> newNode) //새 노드 추가.
    {
        if (head == null) //리스트가 비어있으면 head에 새 노드 할당
        {
            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;
        }
    }

    public void AddAfter(LinkedList_Study3<T> current, LinkedList_Study3<T> newNode) //새 노드를 중간에 삽입
    {
        if (head == null || current == null || newNode == null)
            throw new InvalidOperationException();
        newNode.Next = current.Next;
        current.Next.Prev = newNode;
        newNode.Prev = current;
        newNode.Next = newNode;
    }

    public void Remove(LinkedList_Study3<T> removeNode) //특정 노드 삭제
    {
        if (head == null || removeNode == null) return;
        if (removeNode == head && head == head.Next) //삭제할 노드가 헤드 노드이고, 노드가 1개일 때
            head = null;
        else //아니면 Prev 노드와 Next 노드를 연결
        {
            removeNode.Prev.Next = removeNode.Next;
            removeNode.Next.Prev = removeNode.Prev;
        }
        removeNode = null;
    }

    public LinkedList_Study3<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;
    }

    public int Count()
    {
        int cnt = 0;
        var current = head;
        do
        {
            cnt++;
            current = current.Next;
        } while (current != head);
        return cnt;
    }
}

 

아래는 원형 연결 리스트인지 체크하는 함수

public static bool is_Circular(LinkedList_Study3<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 is_Cyclic(LinkedList_Study3<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;
}

[C# 기초] #18.연결 리스트(Linked List)란? (tistory.com)