이 포스트는 유일하게 JAVA로 작성되었습니다.

선형 리스트

선형 리스트(Linear List)는 자료들이 순서대로 저장되어있는 리스트입니다. 이때 저장된 물리적 순서와 논리적 순서가 반드시 일치해야합니다. 그래서 선형 리스트는 배열로 구현하게 됩니다.

선형 리스트 구현

사실 선형 리스트는 배열이라고 봐도 무방할 정도로 그동안 써왔던 배열을 그대로 이용하게 됩니다. 다음과 같이 크기가 5인 동물들 배열을 만들었습니다.아래와 같은 배열이 존재하고 있는 상태입니다.각 노드에 접근하기 위해서는 데이터가 저장된 위치에 해당하는 인덱스 값을 통해 접근합니다.

이 상태에서 cat과 dog 사이에 snake를 넣는다면 dog와 bear를 각각 인덱스 한 칸씩 뒤로 밀고 삽입해야겠죠. 혹은 dog를 삭제한다면 bear를 한 칸 앞으로 전진시켜 순서대로 저장하는 구조를 가져야합니다.

즉, 삽입은 삽입 지점 이후의 데이터를 한 칸씩 뒤로 밀어낸 다음 삽입하고, 삭제는 데이터를 삭제한 이후에 해당 지점 이후의 데이터들을 앞으로 당겨야합니다.

선형 리스트의 문제점

선형 리스트는 간결하고 직관적이라는 장점이 있습니다. 그러나 그에 따른 문제점도 존재합니다.

자료의 갯수를 알아야한다.

배열로 구현되는 선형 리스트 같은 경우 배열이기 때문에 크기가 정해져 있다는 문제점이 있습니다. 그래서 자료구조 설계를 할 때 자료가 얼마나 많이 담길지를 알아야합니다. 만약 너무 크게 잡는다면 메모리의 낭비가, 너무 적게 잡는다면 메모리 부족으로 인한 에러가 발생하게 됩니다. 그래서 자료의 갯수가 확실하지 않은 이상 선형 리스트의 구현은 어렵습니다.

삽입, 삭제 연산의 효율이 나쁘다.

위에서 언급한 삽입, 삭제 연산에서 데이터를 밀어내거나 당겨야한다고 언급했습니다. 바로 이 과정에서 엄청난 비효율을 보여줍니다. 방금 예시처럼 총 5개의 공간을 가진 작은 배열이면 문제가 없으나 실제로 사용되는 자료의 갯수가 많은 경우가 대다수 입니다. 그래서 이들을 일일히 밀어내고 당기는 과정에서 다른 자료구조(특히 연결 리스트)에 비해서 효율이 매우 나쁩니다.