[자료구조] 리스트 (순차 리스트, 연결 리스트)

리스트란?

리스트는 데이터를 나란히 저장하고 중복된 데이터의 저장을 허용하는 자료구조입니다. 순서의 개념이 없는 집합과는 달리 순서, 위치를 갖고 있습니다. 스택, 큐 또한 리스트를 활용하여 구현된 자료구조입니다.
리스트의 구현 방법으로는 배열을 사용하는 순차 리스트, 메모리의 동적 할당을 기반으로하는 연결 리스트가 있습니다.

순차 리스트

순차 리스트는 배열을 기반으로 리스트를 구현한 방법입니다.

장점

• 데이터의 참조가 쉽다(인덱스 값으로 한번에 참조 가능)

단점

• 연속된 메모리 주소를 할당해야 하기 때문에 배열의 길이가 초기에 결정되어야함
• 삭제의 과정에서 데이터의 이동이 빈번하게 발생

시간 복잡도

데이터 탐색

인덱스를 활용하여 임의 접근이 가능하기 때문에 탐색 과정에 시간 복잡도는 O(1)입니다.

데이터 추가, 삭제

데이터들이 순차적으로 저장되어 있기 때문에 맨 처음 또는 중간 인덱스에 데이터를 삽입, 삭제하기 위해서는 그 뒤에 있는 데이터들을 모두 옮겨줘야합니다. 따라서 이때의 시간 복잡도는 O(n)입니다.
맨 뒤에 데이터를 추가하는 과정은 다른 데이터를 옮길 필요가 없어 이때의 시간 복잡도는 O(1)이 됩니다.

연결 리스트

연결리스트는 데이터를 저장하는 노드와 다음 노드의 메모리 주소를 담고있는 노드로 구성되어 한 줄로 연결되어 있는 방식으로 리스트를 구현한 방법입니다.

장점

• 데이터의 추가, 삭제가 용이
• 리스트의 크기를 자유롭게 조절 가능

단점

• 배열과 달리 연속적인 메모리 주소를 할당받지 않기 때문에 임의 데이터 참조가 어려움

시간 복잡도

데이터 탐색

데이터를 찾기 위해서는 처음부터 순차 접근 방식을 사용하여 탐색해야 하기 때문에 탐색 과정의 시간 복잡도는 O(n)입니다.

데이터 추가, 삭제

데이터를 추가, 삭제하는 과정은 O(1) 입니다. 하지만 맨 앞에 데이터를 추가, 삭제하는 것이 아니라면 그 위치까지 순차 탐색으로 이동해야합니다. 결과적으로 맨앞에 데이터를 추가, 삭제하는 시간 복잡도는 O(1), 그 뒤에 데이터를 추가, 삭제하는 시간 복잡도는 O(n)입니다.