LinkedList의 특성을 설명해주세요.
LinkedList
LinkedList<int> IntLinkedList = new (){1,2,3,4}
- 리스트 내의 각각의 요소들이
node역할을 하며 자신의 앞과 뒤의 node와 연결되어 있다.
IntLinkedList.Count // 포함된 노드 수
IntLinkedList.First // 첫번째 노드
IntLinkedList.Last // 마지막 노드
LinkedListNode<int> intNode = IntLinkedList.Find(1); // 특정 값을 가진 노드 찾기
IntLinkedList.AddAfter(intNode) // 해당 노드 뒤에 추가
IntLinkedList.AddBefore(intNode) // 해당 노드 앞에 추가
IntLinkedList.AddFirst(0) // 첫번째 노드에 값 추가
IntLinkedList.AddLast(0) // 마지막 노드에 값 추가
- 위와 같은 함수를 사용할 수 있으며, 특정 노드에 대해서 중간에 값을 추가, 제거 하는 것에 특화되어 있다.
- 배열과 달리 각각의 노드들은 비연속적이며, 자신의 앞과 뒤에 관한 메모리 주소를 가짐. 따라서 특정 노드를 알고 있을 때 해당 노드의 앞이나 뒤의 노드를 추가 또는 제거하는 과정은 해당 노드의
Previous나 Next 값을 통해 알 수 있으므로 O(1)의 시간복잡도를 가짐
- 특정 노드가 삭제되어도 즉시 메모리가 해제되는 것이 아니라 해당
LinkedList와의 연결이 끊어지는 것이므로 참조는 유지하다가 새로운 노드가 필요할 때 새로운 메모리를 할당하지 않고 연결이 해제된 노드 중에 하나를 재활용하므로 추가 개체 할당이 없음
장단점
- 각각의
LinkedList 내부의 요소들이 자신의 앞과 뒤의 노드를 알고 있으므로 중간에 있는 노드에 접근해 데이터를 삽입 또는 삭제하는 것이 빠르게 이루어짐. 따라서 자주 중간에 있는 요소에 대한 삽입 및 삭제가 이루어지는 경우에 유리함
- 다만 기존 배열만큼 빠르게 인덱스에 접근할 수는 없으므로 상황을 고려하여 적용하는 것이 유리
