연결리스트 시간복잡도 관련 질문드립니다.

Question

MyLinkedList를 제작하면서 C#의 LinkedList의 시간복잡도는 결국 O(1)로 실행되는 것인데, 만약 해당 List를 사용하면서 특정한 값을 찾거나, 제거하고자 할때, 연결리스트의 경우 해당 지점으로 바로 이동할 수단이 없어 Head 부분에서 Tail까지 순차적으로 탐색하여 찾는 방법이기에 O(N)이 시간복잡도가 되어버린다는 것인데, 그렇다면 기존에 말씀하셨던 어떠한 용도로 사용하느냐에 따라 알고리즘의 시간복잡도가 바뀔수 있다는 점이 이 부분에서 나타났다고 보면 될까요? 추가로, 기존에 연결 리스트의 장점으로는 다른 배열과는 다르게 중간에 추가로 방을 생성 할 수 있다는 장점이 있다고 하셨는데, 해당 기능을 어떻게 구현할지는 알겠는데 C# LinkedList의 빠른 함수?(AddLast같은)로 정의된 것은 없을까요? 또한 중간 지점에 값을 넣는 경우도 이전 동적 배열에서 사례와 같이 최악의 경우를 고려해야 하므로 이 기능또한 구현한다면 O(N)으로 생각하면 될까요?

Rookiss · Answer

어떠한 용도라기 보다는, 어떻게 사용하는지에 따라 달라지긴 하죠. 말 그대로 연결 리스트는 아무 조건 없이 O(1)이 아니지만, 보통 연결 리스트를 사용할 땐 이런 부분을 사용자가 고려해서 작업한다 가정합니다. 그 외 부분은 꼭 구글을 통해서 답을 찾아보시기 바랍니다. 구글링은 아무리 강조해도 부족한 정말 중요한 스킬이고 하면 할 수록 요령이 늘어납니다.