연결리스트 (Linked List)

요소 삭제

  1. 일반 배열

    → O(n) 선형시간이 소요된다. 빠지고 나서 빈 공간을 한칸 씩 당겨서 매꿔야하기 때문이다.

  2. 연결 리스트

    → O(1) 삭제 후, 포인터를 그 다음 것으로 옮긴다.

메모리차이

  1. 일반 배열

    ⇒ 메모리를 순차적으로 차지한다.

  2. 연결 리스트

    ⇒ 퍼져있어서 참조하고 있는 메모리를 포인터를 통해 찾는다.

연결리스트 이미지 예시

Untitled

Linked List Data Structure - GeeksforGeeks