컬렉션 프레임워크 실습 { Collection 인터페이스 - List 인터페이스 - LinkedList 클래스 }

LinkedList 클래스

배열은 처음 배열을 생성할 때 정적 크기로 선언하고, 물리적 순서와 논리적 순서가 동일합니다. 배열은 중간에 자료를 삽입하거나 삭제할 때 나머지 자료를 이동시켜 빈 공간을 만들지 않고 연속된 자료 구조를 구현합니다. 또한 처음 선언한 배열 크기 이상으로 요소가 추가되는 경우에는 크기가 더 큰 배열을 새로 생성하여 각 요소를 복사해야 하는 번거로움이 있습니다. 이런 점을 개선한 자료 구조를 Linked List 라고 합니다. 이 자료 구조를 자바는 LinkedList 클래스로 구현하고 있습니다. 

 

LinkedList 클래스 구조

링크드 리스트의 각 요소는 다음 요소를 가리키는 주소 값을 가집니다. 따라서 물리적인 메모리는 떨어져 있어도 논리적으로는 앞뒤 순서가 있습니다. 같은 List 인터페이스를 구현한 ArrayList 에 비해 중간에 자료를 넣고 제거하는 데 시간이 적게 걸린다는 장점이 있고, 크기를 동적으로 증가시킬 수 있습니다. 링크드 리스트의 각 요소는 요소의 자료와 다음 요소의 주소를 저장하는 부분으로 구현됩니다. LinkedList의 각 요소는 물리적으로 다른 메모리에 생성되어 있지만, 다음 요소를 가리키는 순서에 따라 A 다음은 B, 그다음은 D가 됩니다. 마지막 요소는 다음을 가리키는 요소가 없기 때문에 Null이나 0을 저장하게 됩니다. 

 

LinkedList 클래스의 요소 추가 & 제거

LinkedList 는 ArrayList와는 다른 구조 때문에 요소를 추가하고 제거하는 것이 시간이 적게 걸리고 동적으로 배열 크기 변화가 가능합니다. 배열이라면 요소를 중간에 추가할 때 공간을 비운다음 추가하지만 LinkedList는 서로 가리키고 있는 주소 값만 변경해 주면 됩니다. 자료 이동이 필연적으로 발생하게 되는 배열에 비해 훨씬 효율적입니다. 요소의 제거도 마찬가지입니다. 서로 가라키고 있는 주소 값만 변경해주면 되고 제거된 메모리는 자바의 가비지 컬렉터에 의해 수거됩니다. 

 

LinkedList 클래스의 장단점 vs 배열

LinkedList 의 장점은 첫째, 동적으로 요소의 메모리를 생성하기 때문에 배열처럼 용량을 늘리고 요소 값을 복사하는 번거로움이 없다. 둘째, 자료의 추가 및 삭제를 위한 자료의 이동이 배열보다 적다. 그렇다면 배열이 LinkedList 에 비해 가지는 장점은 무엇이 있을까요? 첫째, 요소의 위치를 찾는 것이 빠릅니다. 어떤 요소의 위치를 찾을 때를 생각해 봅시다. 배열은 물리적으로 연결된 자료 구조이므로 i 번째 요소 메모리 위치를 바로 계산할 수 있어서 접근이 빠릅니다. 둘째, 구현이 쉽습니다. 이런 특징 때문에 사용하는 자료의 변동(삽입 & 삭제)이 많은 경우에는 LinkedList 를 자료 변동이 거의 없는 경우에는 배열을 사용하는 것이 효율적입니다. 

 

LinkedList 클래스 사용하기

LinkedList 는 ArrayList 보다 다양한 메서드를 제공합니다. LinkedList 가 제공하는 메서드를 사용해보겠습니다.

LinkedList 클래스에는 addFirst( ), addLast( ), removeFirst( ), removeLast( ) 등의 메서드가 있습니다. 이런 메서드들은 스택 stack이나 큐 queue에서 다양하게 활용할 수 있습니다. 위 코드의 출력 화면을 살펴보겠습니다.