[자료구조] 선형 리스트(Linear List) 개념 이해하기
선형 리스트(Linear List)란?
선형 리스트란 순서를 가지고 일렬로 나열한 데이터의 모임이다. 가장 간단한 형태의 자료구조이다.
표현하고자하는 논리적인 순서와 실제 메모리상에 저장되는 물리적인 순서가 동일하다.
집합과 비슷하지만 데이터가 순서를 가지고 있다는 게 다르고 배열과 비슷하지만 인덱스 값이 식별자가 아니라는 것이 다르다.
배열은 인덱스 값을 식별자로 가지기 때문에 원소를 삭제했을 때 삭제된 데이터의 자리를 비워두는데 이런 구조가 메모리의 낭비를 유발한다. 반면에 리스트는 인덱스 값을 식별자로 가지기 않기 때문에 원소가 삭제되면 뒤 원소로 빈틈없이 채워넣는다. 그 결과 리스트는 배열에 비해 메모리의 낭비가 적다.
배열과 같이 랜덤 엑세스가 가능하므로 특정 위치의 데이터에 접근하는 시간복잡도는 O(1)이다.
순차 선형 리스트는 데이터의 물리적 순서와 논리적 순서의 일치를 위해 삽입 연산 시 삽입되는 데이터를 위한 빈자리를 만들고, 삭제 연산 시 삭제된 데이터의 빈자리를 채우기 때문에 자료의 이동 작업이 일어나고 이로 인해 오버헤드가 발생할 수 있다. 따라서 삽입, 삭제 연산이 빈번한 경우에는 선형 리스트를 사용하지 않는 것이 좋다
#오버헤드 링크 추가
선형 리스트의 삽입
선형 리스트는 연속된 메모리 공간에 저장되어 있기 때문에 요소(elements)를 삽입하기 위해서는 리스트의 마지막에 데이터를 삽입할 것이 아니라면, 빈자리를 만들어준 후에 요소를 삽입해야한다. 자리를 만들기 위해서는 삽입할 위치 이후의 요소들을 모두 한 요소의 크기만큼 뒤로 밀어줘야 한다.
리스트의 2번 위치에 5의 값을 삽입해주는 과정이다.
- 리스트 2번의 자리를 비워줘야한다, 빈자리를 만들기 위해 2번을 포함한 뒷자리, 즉 n>=2인 n번째 자리의 요소들을를 한자리씩 뒤로 이동시킨다.
- 빈자리에 4의 값을 삽입해준다.
k개의 요소를 가진 리스트라면 빈자리를 만들기 위한 요소들의 이동 횟수는 n부터 k까지의 요소들을 모두 이동시켜줘야함으로 n-k+1이 된다. 즉 (리스트의 길이 - 삽입 위치 + 1)이 된다
선형 리스트의 삭제
선형 리스트는 논리적 순서와 물리적 순서가 일치하는 순차 자료구조이기 때문에 원소가 삭제되서 생긴 빈자리를 용납하지 않는다. 만약 요소를 삭제해 빈자리가 생기면 뒤의 요소들을 모두 요소 하나의 크기만큼 앞으로 이동시켜 빈자리를 채운다.
리스트의 2번 위치에 존재하는 5의 값을 삭제해주는 과정이다.
- 리스트의 2번 위치에 존재하는 5의 값을 삭제해준다
- 빈자리를 채우기 위해 2번 이후의 뒷자리, 즉 n>2인 n번째 자리의 한자리씩 앞으로 이동시킨다.
k개의 요소를 가진 리스트라면 빈자리를 채우기 위한 요소들의 이동 횟수는 n+1부터 k까지이 요소들을 모두 이동시켜줘야함으로 k - (n+1) + 1 = k - n가 된다. 즉 (리스트의 길이 - 삭제 위치)가 된다.