[자료구조] Linked List

Linked List

Linked List는 Node라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address를 저장한다.

Linked List는 물리적인 메모리상에서는 비연속적으로 저장되지만, 이를 구성하는 각각의 Node가 다음 Node의 address를 가리킴으로써 논리적인 연속성을 갖는 자료구조이다. 또한, 데이터가 추가되는 시점에 메모리를 할당하기 때문에 메모리를 좀 더 효율적으로 사용 할 수 있다는 장점이 있다.

데이터 삽입/삭제

Array List의 경우, 중간에 데이터를 삽입/삭제하게 되면 해당 인덱스의 뒤에 있는 모든 원소들을 shift 하기 때문에 O(n)의 시간복잡도를 갖게 된다. 하지만 Linked List는 물리적으로 옮길 필요없이 next address가 가리키는 주소값만 변경하면 되기 때문에 O(1)의 시간복잡도로 삽입/삭제가 가능하다.

데이터 검색의 경우, Array List는 인덱스로 해당 원소에 접근하기 때문에 O(1)의 시간복잡도를 갖지만, Linked List는 첫 번째 Node부터 순차적으로 확인하기 때문에 O(n)의 시간복잡도를 갖는다.

삽입

삭제