C# 선형 자료구조 - 연결리스트(LinkedList)

• 연결리스트(Linked List)

• 단순 연결 리스트(Singly Linked List) : 모든 데이터 타입을 가져올 수 있음

 

- ArrayList는 중간에 데이터를 추가/삭제 시 맨 뒤에 새로운 칸을 생성 후 한 칸씩 밀어내서 작업(시간이 오래걸림)

 

- Linked List는 중간에 데이터를 바로 추가/삭제 할 수 있기 때문에 작업이 빠름

- 추가 데이터에 대한 연산 불필요, 구현의 어려움, 탐색 연산의 비용이 높음

 

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

- 양방향 탐색이 가능

- 노드에 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있다.

LinkedList<int> number = new LinkedList<int>();
number.AddFirst(10); //10
number.AddLast(20); //10, 20
number.AddLast(30); //10, 20, 30
number.AddFirst(9); //9, 10, 20, 30

//노드 찾기
LinkedListNode<int> nodeTemp = number.Find(20);

number.AddAfter(nodeTemp, 21);
number.AddBefore(nodeTemp, 19);

//삭제
number.Remove(10);

//검색
for(var node = number.First; node != null; node = node.Next)
{
	Console.WriteLine(node.Value);
}

 

• 원형 연결리스트(Doubly Circular Linked List)

- 처음과 마지막 노드를 서로 연결

- 마지막 노드의 Next는 첫번째 노드를 가리키고 있음

- 첫번째 노드의 Previous는 마지막 노드를 가리키고 있음

 

ArrayList, List<T>	LinkedList<T>
- 데이터 검색에 유리 - 데이터 추가/삭제가 느림	- 데이터 추가/삭제가 빠름 - 데이터 검색이 느림(처음부터 탐색해야 하기 때문)