선형리스트란?
선형리스트란 순차리스트라고도 부르며 리스트에 나열된 데이터들이 순서를 가지고 있다.
선형리스트의 데이터들이 저장되는 순서대로 나열 될 순서가 정해진다.
예를들어,
[0] [1] [2]
사과 바나나 키위
배열에 세가지 데이터를 저장할때 메모리에 저장되는 순서와 동일하게 저장된다.
선형 리스트에서 데이터 추가 삭제
이전에 말했듯이 데이터에는 순서가 있으므로 중간에 삽입 하기를 원할 때 데이터에 순서를 해치지 않아야한다.
추가나 삭제를 할때는기존의 데이터들의 순서를 해치지 않고 원하는 위치에 데이터를 넣거나 삭제해야한다.
삭제할 때는 삭제된 데이터의 자리를 비우지 않기 위해 데이터를 옮겨야한다.
아래 배열의 1자리에 오렌지를 추가해 보자
[0] [1] [2]
사과 바나나 키위
▼
[0] [1] [2] [3]
사과 바나나 키위
▼
[0] [1] [2] [3]
사과 바나나 키위
▼
[0] [1] [2] [3]
사과 오렌지 바나나 키위
기존에 데이터가 저장되었던 순서를 해치지 않기 위해 자리를 확보하고 차례대로 데이터를 옮겨준다.
방금 추가 했던 오렌지를 삭제해 보자
[0] [1] [2] [3]
사과 오렌지 바나나 키위
▼
[0] [1] [2] [3]
사과 바나나 키위
▼
[0] [1] [2] [3]
사과 바나나 키위
▼
[0] [1] [2] [3]
사과 바나나 키위
선형 리스트는 가장 기본적이면서 단순한 자료구조이다.
또, 접근속도가 빠르다는 것을 장점으로 두고있다.
하지만, 위의 예제들로 미루어 보았을 때 데이터를 추가나 삭제할 때 과정이 까다롭다.
맨뒤에 데이터를 추가/삭제를 할 경우 빠르겠지만, 앞 쪽의 데이터를 추가나 삭제를 할 경우 데이터들의 순서를 유지시키기위해 데이터들을 옳기는 과정이 길어져 오버헤드가 발생할 수 있다.
