#배열리스트와 연결리스트의 차이

리스트에는 두가 종류가 있다. 배열리스트와 연결리스트이다.

배열리스트는 일반적으로 인덱스에 기초해서 데이터에 접근하므로 데이터 검색이 용이하다.

그러나 배열은 생성 시 크기가 지정되어야 하므로, 새로운 데이터의 추가나 삭제와 같은 수정 작업이 필요할 경우 크기를 재할당 해야한다. 예를 들어, { 1, 2, 4, 5, 6 } 와 같은 데이터 셋이 있을 때, 2 다음에 3을 추가하고 싶다면 나머지 4, 5, 6의 데이터는 모두 한칸 씩 뒤로 밀어내야 한다. 

따라서 검색 보다는 수정 작업이 많이 요구되는 데이터 셋에 대해 연결리스트가 배열리스트보다 적합하다. 

연결리스트는 메모리 상에서 데이터의 연속적 배치를 보장하지는 않지만, 특정 데이터 기준으로 전후의 다른 데이터의 메모리 위치를 기억한다. 앞에서 든 예에서 처럼 3을 추가한다고 한다면, 변경 대상 노드의 참조 주소만 변경하면 되므로 비교적 간단하게 변경 작업이 가능하다. 

그러나 연결리스트는 앞에서 말한 바와 같이 메모리 상에 비연속적으로 데이터가 배치될 수 있으므로 인덱스를 이용한 접근은 할 수 없다. 

즉, 3이라는 데이터를 검색하고 싶다면 배열리스트에서는 list[2]처럼 접근이 가능하지만, 연결리스틑 불가능하다. 따라서 연결리스트에서의 특정 데이터의 검색은 반드시 처음부터 시작해 데이터를 비교하면서 진행하게 되므로 느릴 수 밖에 없다.