링크드 리스트 in java

배열은 데이터를 물리적 주소에 순차적으로 저장하고 인덱스를 가지고 있어 탐색 시 바로 접근할 수 있기 때문에 접근 속도가 빠르다.

그러나, 배열은 크기가 고정되어 있어 배열의 크기를 초과하면 배열의 크기를 늘리거나 배열을 복제해야한다.

데이터 삽입/삭제 시 해당 위치 다음칸에 있는 데이터를 모두 한칸씩 뒤로 밀거나 앞으로 당겨오는 연산을 해야하므로 속도가 오래걸린다.

 

 

연결리스트는 데이터와 다음 데이터의 물리적 주소까지 같이 저장한다. 이를 노드라고 하고, 배열과 달리 크기에 제한이 없다.

(단순 연결리스트는 다음 데이터의 주소를, 이중 연결리스트는 이전 주소와 다음 주소를 모두 저장)

특정 데이터에 접근할 때 인덱스로 바로 접근할 수 있었던 배열과 달리 첫 노드부터 원하는 노드까지 링크를 따라가야
접근이 가능하기 때문에 배열에 비해 접근 속도는 떨어진다.
반면, 데이터를 삽입/삭제 시 앞/뒤 노드의 주소만 변경하면되기 때문에삽입/삭제는 배열보다 빠르다.

java에서는 링크드 리스트를(연결리스트) 컬렉션 클래스로 표현할 수 있다.