[Java 활용] 3.7 LinkedList 클래스

Java 언어에서 LinkedList는 연결리스트를 구현한 클래스입니다. Vector와 ArrayList 클래스처럼 List 클래스를 기반으로 파생한 클래스입니다. 그리고 연결리스트도 배열처럼 선형 자료구조입니다. 하지만 배열은 저장소가 연속적인 메모리에 하나의 덩어리로 할당받지만 연결리스트는 노드 하나에 하나의 데이터를 보관하고 노드 내의 링크에 의해 순서 정보(다음 노드의 위치 정보, 이전 노드의 위치 정보)를 기억하는 자료구조입니다.

배열과 연결리스트
배열과 연결리스트

LinkedList 클래스도 Vector와 ArrayList처럼 List 클래스를 기반으로 파생한 클래스이므로 당연힌 Collection 인터페이스에 약속한 기능을 구현하고 있습니다. 이는 사용방법이 흡사하다는 의미입니다. 하지만 내부적으로 살펴보면 Vector나 ArrayList는 내부 저장소가 배열 형태여서 인덱스 연산에 들어가는 비용이 적습니다. 대신 특정 위치에 추가하거나 삭제하는데 비용이 많습니다. LinkedList는 연결리스트를 구현한 것이어서 인덱스 연산의 속도가 매우 좋지 않습니다. 대신 특정 위치에 추가, 삭제하는데 비용이 O(1)입니다. 그리고 서로 다른 컬렉션을 하나로 병합하거나 분리하는 비용이 적습니다. 이와 같은 주요 특징은 자료구조에 관한 레퍼런스를 참고하시기 바랍니다.

 

다음은 3.4에서 다루었던 소스 3.4에서 Vector 개체를 생성하는 부분만 LinkedList로 변경한 코드입니다. 다른 부분에 코드를 변경하지 않아도 잘 동작하는 것을 알 수 있습니다.

 

▷ 소스 3.9 LinkedList를 이용한 회원 관리 프로그램

▷ 소스 3.9 실행 결과

이 책에서 Vector, ArrayList, LinkedList 클래스를 사용하는 프로그램을 같은 형태로 작성한 이유는 인터페이스 기반으로 프로그래밍할 때의 장점을 명확히 보여주기 위한 것이 첫 번째 이유입니다. 그리고 두 번째 이유는 비슷한 역할을 하는 클래스들이 있을 때 가급적 공통적인 기능을 이용해서 작성하며 변경 비용을 줄일 수 있다는 것을 얘기하기 위해서입니다. 특정 컬렉션으로 구현해야 할 당위성이 없다면 미래의 유지 보수를 줄일 수 있게 공통적인 기능을 사용하는 습관을 갖기 바랍니다. 물론 성능이나 다른 특정 목적이 있다면 다른 선택을 해야 할 수도 있겠죠.