선형 리스트와 연결 리스트의 차이

프로그래밍/자료구조

argentdarae 2025. 3. 12. 23:07

선형 리스트와 연결 리스트란?

선형 리스트란 연속된 메모리 공간에 데이터를 저장하는 리스트이다

연결 리스트란 각 요소가 데이터의 다음 요소의 참조(포인터)를 가지는 리스트이다. 다음 요소의 참조만 알면 되기 때문에 연속된 메모리 공간이 필요 없다

선형 리스트는 연속된 메모리 공간을 사용한다. 연결 리스트는 불연속적이며 포인터로 연결되어있다

선형 리스트는 인덱스를 모를 경우 O(n), 인덱스를 알 경우 O(1)이다

연결 리스트도 인덱스를 모를 경우 O(n), 인덱스를 알아도 해당 인덱스에 해당하는 요소의 메모리가 어디있는지 모르므로 O(n)이다

선형 리스트는 맨 마지막 인덱스에 작업을 수행하며 Capacity가 초과되지 않는 경우 O(1)이다

그 외의 경우는 순차적인 요소 이동이 있거나 Resize가 일어난다면 O(n)이다

연결 리스트는 해당 노드를 알고 있을 때는 O(1), 삽입/삭제 지점을 찾기 위한 탐색이 선행되어야 한다면 O(n)이다

선형 리스트의 경우 동적으로 크기가 제어된다. 만약 Count가 Capacity 이상으로 올라간다면 내부적으로 배열을 새로 할당(Resize)해야 하므로 추가적인 메모리 할당 비용이 발생하기 때문이다

연결 리스트의 경우 크기가 정해져 있지 않다. 요소가 늘어나면 늘어날 수록 메모리 사용이 증가하기 때문이다

또한 각 요소마다 추가적인 포인터(주소) 공간이 필요하기 때문에 추가 메모리가 필요하다

선형 리스트의 경우 데이터의 개수가 고정되거나 최대 길이를 미리 특정할 수 있는 경우, 혹은 삽입/삭제보다 데이터에 대한 접근(검색)이 더 자주 이루어져야 하는 경우 사용된다

연결리스트는 최대 길이를 미리 특정할 수 없고 삽입/삭제가 빈번할 경우 사용한다