CH11-12~14 LinkedList

[자바의 정석 - 기초편] ch11-12~14 LinkedList

이번시간에는 linkedlist를 배울 것이다. 그전에 배열의 장단점을 알아보자.

배열의 장점은 구조가 간단하고, 데이터에 엑세스하는데 접근시간(access time)이 짧다는 것이다.

그리고 데이터가 연속적으로 저장되어 있다. 인덱스만 주어지면 어느곳이든 액세스하는시간이 동일함. 인덱스 주소가 100이면, offset * 타입사이즈 해서 바로 주소를 얻을 수 있기 때문임.

단점은 한번 생성하면 런타임동안 크기를 변경할 수 없다는 것임. 배열의 크기를 늘리려면 새로운 배열을 만들고 복사해줘야 한다. 그리고 참조변경까지 해줘야 함.

그리고 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다. 배열 중간의 데이터를 삭제하거나 추가하는 것을 말함. 이때 모든 데이터가 인덱스를 옮겨야 해서 시간이 많이 걸린다…

물론 순차적인 추가와 삭제는 빠르다.(끝 인덱스에 추가 및 삭제)

linkedlist는 배열의 단점을 보완하기 위해 등장했다.

linkedlist는 주소가 불연속적으로 존재하는 데이터를 연결한 구조이다.

배열은 각 데이터의 주소가 연속적(붙어있다.)이다.

링크드 리스트는 각 데이터의 주소가 불연속적이다.

이때 각 요소를 노드(node)라고 부른다. 각 노드는 다음노드의 주소를 담은 참조변수를 갖고 있다.

linkedlist는 비순차적인 데이터의 추가 삭제가 참조변경으로 가능하다..