[ 자료구조 ] linked list의 삽입/삭제는 정말 array list보다 빠른가?

의문점

  연결 리스트의 경우 삽입/삭제 자체는 O(1)의 시간 복잡도를 가지지만, 대상이 되는 인덱스 까지 찾아가는 과정을 고려한다면 O(n)의 시간 복잡도가 추가된다고 볼 수 있는데 이를 단순히 O(n + 1)이라 가정한다면 O(n)의 시간 복잡도를 가지는 배열 리스트보다 빠르다고 할 수 없지 않는가?

 

결론

  배열 리스트의 경우 특정 인덱스에 요소를 삽입 / 삭제할 경우 해당 인덱스 이후 모든 요소의 위치를 이동시켜야 한다. 따라서 일정하게 O(n)의 시간 복잡도를 갖는다. 하지만 연결 리스트의 경우 head 부분에 가까워질수록 시간복잡도는 O(1)에 가까워진다. 즉, 삽입/삭제의 대상이 될 인덱스의 위치에 따라 O(1) ~ O(n)의 시간 복잡도를 갖는다. 결론적으로 연결리스트는 배열 리스트보다 빠르거나 비슷한 속도를 보이며, 리스트의 타입에 따라서 시작이나 끝 부분에서 삽입/삭제 오퍼레이션이 자주 일어날 경우 보다 효율적으로 동작 가능하다.