배열/배열리스트/연결리스트

배열(Array)
  -  배열은 데이터를 논리적 순서에 따라 순차적으로 데이터를 입력하며, 물리적 주소 또한 순차적이다. 메모리 할당이 연속적이어서 인덱스를 사용하면 원하는 데이터를 한번에 접근이 가능하기 데이터 접근 속도가 매우 빠르다. 하지만 메모리 관리면에서 공간 낭비가 심하다. 또한 배열은 데이터의 삽입/삭제에는 취약하다. 배열 특성상 데이터 삽입/삭제가 이루어지면 삽입/삭제가 이루어진 위치의 다음부터 모든 데이터의 위치를 변경해야 하기 때문이다.만약 배열 데이터의 수가 10000개라고 하고 삽입/삭제가 빈번하게 일어난다고 가정을 하고 생각을 하면 프로그램은 데이터 삽입/삭제 때마다 데이터의 위치를 바꾸는데만 많은 자원을 사용할 것이다. 이것은 매우 비효율적이다.

 

배열리스트(ArrayList)
 -  배열리스트는 배열의 특징인 인덱스를 사용하여 각각의 값에 바로 접근할 수 있다. ArrayList는 중간에 끼워 넣으려면 끼워 넣고 싶은 위치 다음에 있는 자료들을 한 칸씩 미뤄야 하는 단점이 있다. 유형의 객체만 만들면 추가 제거시 자동으로 크기가 변한다. Array와 다르게 ArrayList는 객체이다. 즉, 인스턴스 변수(상태)와 메소드(행동)를 가지고 있다.

 

연결리스트(LinkedList)
  -  연결리스트는 데이터를 논리적 순서에 따라 데이터를 입력한다. 하지만 물리적 주소는 순차적이지 않다. 메모리 할당이 비연속적이고, 크기가 동적이기 때문에 낭비가 없다. 인덱스를 가지고 있는 배열과는 달리 연결리스트는 인덱스 대신 현재 위치의 이전 및 다음 위치를 기억하고 있다. 한번에 데이터 접근이 가능하지 않고 데이터가 많은 경우에 처음 자료부터 순차적으로 연결되어 있는 링크를 따라가며 접근해야 되기 때문에 배열에 비해 속도가 떨어진다. 하지만 데이터 삽입/삭제는 논리적 주소만 바꿔주면 되기 때문에 데이터 삽입/삭제는 용이하다. 삽입/삭제가 이루어지는 데이터의 링크만 변경하면 되므로 배열같이 다른 데이터에 영향을 많이 주지 않는다.