리스트의 개념
배열과 리스트의 차이
배열은 인덱스로 표현되는 순서가 배열 원소의 메모리 공간에서 물리적 의미를 의미한다.
반면 리스트의 순서 개념은 어떤 정의에 의해 결정된 논리적인 순서이다. 원소들의 물리적인 저장 순서나 위치와 무관하게 원소들 간의 논리적인 순서만 유지한다.
쉽게 말하면 배열의 경우 데이터가 연속된 메모리 공간에 할당되고 리스트의 경우에는 메모리가 연속적인 공간에 있지 않고 다음 노드를 가리키는 주소값을 가지고 있다.
리스트의 종류
1. 포인터를 이용한 방법
원소값을 저장하는 공간과 다음 원소를 가리키는 위치 정보를 저장하는 공간을 같이 구현하는 방법이다.
2. 배열을 이용한 방법
배열을 만들어놓고 중간에 데이터를 삽입하려면 삽입하려는 위치 뒤에 있는 데이터를 다 한 칸씩 뒤로 밀고 삽입해야 한다는 엄청난 단점이 있다. 삭제할 때도 삭제하려는 위치 뒤에 있는 데이터를 한 칸씩 앞으로 땡겨야 한다.
이러한 동작들은 원소의 수에 비례해서 프로그램 수행 시간을 엄청나게 증가시킬 수 있다.
강승구