2024.03.13 - LinkedList

• 연결 리스트(Linked List)

연결 리스트란, 노드들이 한 줄로 연결되어 있는 방식으로 구성된 자료구조이다.

각 노드는 데이터와 다른 노드를 가리키는 포인터로 구성되어 있다.

 

 

 

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

단일 연결 리스트는 단방향으로 노드들을 연결한 자료구조이다.

각 노드의 포인터는 다음 노드를 가리킨다.

 

 

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

이중 연결 리스트는 양방향으로 노드들을 연결한 자료구조이다.

각 노드는 이전 노드와 다음 노드를 가리키는 포인터 2개를 가지고 있다.

때문에 양방향으로 탐색이 가능하다.

 

 

 

• C#의 LinkedList

C#에서는 LinkedList<T> 클래스를 통해 Double Linked List로 구현된 자료구조를 제공한다.

 

- LinkedList 선언 방법

LinkedList<자료형> 객체_이름 = new LinkedList<자료형>();

 

 

- LinkedListNode 선언 방법

LinkedListNode<자료형> 객체_이름 = new LinkedList<자료형>(데이터);

 

LinkedList의 요소는 데이터가 아닌 데이터를 포함한 노드이다.

LinkedListNode는 LinkedList에 들어갈 노드 객체를 만들어 준다.

 

 

- LinkedList의 시작과 끝에 노드(요소) 추가하기 (AddFirst / AddLast)

연결_리스트.AddFirst(노드)        //LinkedList의 시작위치에 지정한 새 노드를 추가.
연결_리스트.AddLast(노드)        //LinkedList의 끝에 지정한 새 노드를 추가.

 

비어있는 myLikedList에 "데이터0"을 담은 노드 node0가 먼저 추가되고, "데이터1"을 담은 노드 node1이 myLinkedList의 시작위치에 추가되었다. 

 

AddFirst와 AddLast는 노드 말고 데이터를 인수로 받을 수 있게 오버로딩 되어있다.

데이터를 인수로 받으면 해당 데이터가 포함된 노드를 알아서 생성해서 LinkedList에 추가해준다.

연결_리스트.AddFirst(데이터)        //LinkedList의 시작위치에 지정한 데이터가 포함된 새 노드를 추가.
연결_리스트.AddLast(데이터)        //LinkedList의 끝에 지정한 데이터가 포함된 새 노드를 추가.

 

 

AddFirst(데이터) / AddLast(데이터)는 리턴 값을 가진다. 리턴 값은 LinkedList에 추가해준 새 노드 LinkedListNode이다. 리턴 값인 노드를 대입하지 않고 위 코드처럼 날려버리면 나중에 노드를 통해 LinkedList를 참조할 때 문제가 생긴다. 따라서 아래와 같이 코드를 작성하여 노드의 정보를 남겨두어야 한다.

 

 

- LinkedList의 중간에 노드 추가하기(AddAfter / AddBefore)

연결_리스트.AddAfter(기준노드, 새_노드)           //LinkedList의 지정한 기준노드 뒤에 새 노드 추가.
연결_리스트.AddAfter(기준노드, 데이터)             //LinkedList의 지정한 기준노드 뒤에 값을 가진 새 노드 추가.
연결_리스트.AddBefore(기준노드, 새_노드)        //LinkedList의 지정한 기준노드 앞에 새 노드 추가.
연결_리스트.AddBefore(기준노드, 데이터)          //LinkedList의 지정한 기준노드 앞에 값을 가진 새 노드 추가.

 

 

- LinkedList의 속성 (Count / First / Last)

연결_리스트.Count        //LinkedList에 실제로 포함된 노드의 수를 가져옴.
연결_리스트.First           //LinkedList의 첫 번째 노드를 가져옴.
연결_리스트.Last           //LinkedList의 마지막 노드를 가져옴.

First와 Last 출력이 뭔가 이상하다

 

myLinkedList.First와 myLinkedList.Last를 출력하면 "데이터0"과 "데이터3"을 출력할 것 같았지만, 이상한 값이 출력된다. First와 Last로 가져오는 것은 노드가 가지고 있던 데이터가 아니라 노드 그 자체이다. 노드가 가진 데이터를 얻고 싶다면 노드의 속성에 접근해야 한다.

 

 

- LinkedListNode의 속성

연결_리스트_노드.Value             //노드에 포함된 값을 가져옴.
연결_리스트_노드.ValueRef        //노드에서 보유한 값에 대한 참조를 가져옴.
연결_리스트_노드.Next               //LinkedList의 해당 노드 다음의 노드를 가져옴.
연결_리스트_노드.Previous        //LinkedList의 해당 노드 이전의 노드를 가져옴.
연결_리스트_노드.List                //노드가 속한 LinkedList를 가져옴.

 

 

- LinkedList의 노드 제거하기(Remove / RemoveFirst / RemoveLast)

연결_리스트.Remove(노드)            //LinkedList에서 지정된 노드를 제거.
연결_리스트.Remove(데이터)        //LinkedList에서 맨 처음 발견되는 지정된 값을 제거. (오버로딩 되어있음)
연결_리스트.RemoveFirst()            //LinkedList의 시작 위치의 노드를 제거.
연결_리스트.RemoveLast()            //LinkedList의 끝 위치의 노드를 제거.

 

 

• LinkedList의 특징

List가 데이터를 삽입/제거 할 때

 

LinkedList가 데이터를 삽입/제거 할 때

 

LinekdList는 List에 비해 데이터 삽입/제거 과정이 간단하다는 장점이 있지만, 인덱스로 참조가 불가능하고 List에 비해 탐색 과정이 길다는 단점이 있다.