[자료구조] 연결 리스트(Linked List)

Linked List 란?

-데이터를 포함하는 노드들을 연결하여 컬렉션을 만든 자료 구조

-각 노드는 데이터와 다음/이전 링크 포인터를 갖게 된다.

-단일 연결 리스트(Singly Linked List)는 노드를 다음 링크로만 연결한 리스트

-이중 연결 리스트는 각 노드를 다음 링크와 이전 링크 모두 연결한 리스트

-Circular Linked List(순환 연결 리스트)는 마지막 노드의 다음 링크가 맨 처음 노드를 가리키게 연결한 리스트

 

LinkedList<T> 클래스

-.NET에서 LinkedList 클래스는 이중 링크드 리스트로 구현되어 있다.

-LinkedListNode 클래스는 리스트 노드를 표현한다.

-AddFirst, AddLast, AddBefore, AddAfter등으로 링크스 리스트 맨 앞, 맨 뒤 혹은 특정 노드의 앞, 뒤에 새 노드를 추가할 수 있다.

 

사용 예제

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        LinkedList<string> linkedList = new LinkedList<string>();
        linkedList.AddLast("You");
        linkedList.AddLast("So Much");
        linkedList.AddFirst("I");
        
        LinkedListNode<string> tempNode = linkedList.Find("I");
        LinkedListNode<string> newNode = new LinkedListNode<string>("Love");
        
        //tempNode 뒤에 newNode 추가
        linkedList.AddAfter(tempNode, newNode);
        
        foreach(var node in linkedList)
        {
            Console.WriteLine(node); //I Love You So Much 순서대로 출력
        }
    }
}