링크드 리스트 ( LinkedList )
LinkedList<T> 는 C# 에서 제공하는 자료구조의 연결 리스트의 구현체이다.
이중 연결 리스트 ( Double Linked List ) 로 구성되어 있다.
링크드 리스트에서 노드 ( Node ) 는 가장 작은 단위, 즉 데이터를 담는 상자를 말한다.
노드 ( Node ) 의 구성
노드는 2가지 정보를 가지고 있다.
[ 데이터 | 다음 노드 주소 ] -> [ 데이터 | 다음 노드 주소 ] -> [ 데이터 | null ]
1. 데이터 ( Data , 값 )
- 저장하고 싶은 값
- 예시 : 정수형 10 , 문자열 "호찬" , 객체 Player 등등..
2. 링크 ( Link, 참조 / 포인터 )
- 다음 노드 ( Node ) 를 가리키는 정보
- 단일 연결 리스트 : Next
- 이중 연결 리스트 : Prev , Next
- 원형 리스트 : Next 가 다시 처음 노드를 가리키기도 한다.
링크드 리스트 ( LinkedList ) 선언 방법
C# 은 제네릭 클래스 LinkedList<T> 를 기본 제공한다.
그냥 사용하면 되고 직접 구현할 필요가 없다.
선언 & 초기화
// 정수형 링크드 리스트
LinkedList<int> numbers = new LinkedList<int>();
// 문자열형 링크드 리스트
LinkedList<string> list = new LinkedList<string>();
list.AddLast("W");
list.AddLast("A");
list.AddLast("S");
list.AddLast("D");
//또는 생성자에서 초기화 가능
LinkedList<string> list = new LinkedList<int>(new[] { 10, 20, 30 });
값 추가
numbers.AddFirst(5); // 맨 앞에 삽입
numbers.AddLast(15); // 맨 뒤에 삽입
LinkedListNode<int> node5 = numbers.First;
numbers.AddAfter(node5, 15); // 5 뒤에 15 삽입
값 삭제
numbers.Remove(15); // 특정 값 삭제
numbers.RemoveFirst(); // 맨 앞 삭제
numbers.RemoveLast(); // 맨 뒤 삭제
언제 사용하면 좋은가?
자주 생성되고 사라지는 객체 컬렉션 : 애니팡 , 총알 등 중간 제거가 잦을 때
대형 리스트에서 중간 삽입 / 삭제 가 빈번하고, 인덱스 접근은 거의 없을 때
- 반대로 랜덤 인덱스 접근이 많으면 List<T> ( 동적 배열 ) 가 훨씬 유리하다.
배열과 무엇이 다른가?
1. 저장 위치
- 배열 : 메모리에 연속적으로 배치
- 링크드 리스트 : 흩어져 있지만 포인터로 연결
2. 접근과 탐색
- 배열 : 인덱스만 알면 바로 원하는 원소에 접근 가능
- 링크드 리스트 : 원하는 원소를 찾으려면 앞에서부터 이동해야함
3. 삽입과 삭제
- 배열 : 중간 삽입 / 삭제는 뒤 요소들을 밀어야한다.
- 링크드 리스트 : 노드 참조만 바꾸면 된다. ( 참조를 끊으면 GC 가 알아서 수거 )
정리
- 배열은 칸 하나하나가 데이터만 저장하지만
- 링크드 리스트는 노드라는 상자가 데이터 + 다음 노드 주소까지 함께 저장된다.
- 노드끼리 연결되면서 전체가 하나의 리스트가 된다.
참고 자료
https://learn.microsoft.com/ko-kr/dotnet/api/system.collections.generic.linkedlist-1?view=net-8.0