Linked List란?

🤓오늘의 공부 주제: Linked List🤓

Q. Linked List는 어떤 자료구조인가?

A. Linked List는 Node라는 구조체로 이루어져 있는데, Node는 데이터 값과 다음 Node의 address를 저장. Linked List는 물리적인 메모리 상에서는 비연속적으로 저장되지만 각각의 노드가 다음 노드의 주소를 가리킴으로써 논리적 연속성을 가진 자료구조.

🔑key point!

메모리상에서는 불연속 데이터 저장. 그러나 노드의 다음 주소값을 통해 불연속 데이터를 연결하여 논리적 연속성을 보장. 또한 데이터 추가 되는 시점에 메모리 할당을 통해 효율적 메모리 사용.

논리적 연속성을 위해 다음 주소를 추가적으로 저장해야해서 데이터 하나 당 메모리 크기는 큼.

데이터 삽입 삭제시 물리적으로 옮길 필요 없이 다음 주소값만 변경하면 되기 때문에 O(1). 그러나 탐색을 위해서는 바로 인덱스로 접근 불가능하고 순차 탐색해야해서 O(n).

출처 : 인프런 - 기출로 대비하는 개발자 전공면접 [CS 완전정복]