● LinkedList
ArrayList와 마찬가지로 List를 상속받는 컬렉션 클래스이다. List를 상속받으므로 데이터의 저장 순서를 유지하고, 데이터의 중복을 허용한다. LinkedList는 기존의 배열의 단점을 보완한 새로운 자료구조이다.
우선, 기존의 배열(Array)의 단점이 무엇이었나?
- 크기를 변경할 수 없다.
- 중간에 존재하는 요소의 삭제 또는 요소의 추가가 어렵다(시간이 많이 걸린다.)
사실 1과2는 서로 깊은연관이있다. 배열의 크기를 변경할 수 없기때문에 중간에 요소를 추가하거나 삭제하려면 새로운 배열을 생성하여 복사해야하기 때문이다. 그렇다면 LinkedList는 이러한 배열(Array)의 단점을 어떻게 보완하였고 차이점은 무엇이며, 왜 사용하는지에 대해서 알아보자.
● Array와 LinkedList의 데이터 구조의 차이
배열(Array)은 데이터가 연속적으로 연결되어 있고 데이터마다 index가 주어져있는 형태이다.
반면에 LinkedList는 각요소에 node라는 클래스가 존재하고 이 node에는 데이터를 저장하고 있는 node와 다음 요소의 주소가 저장되어 있는 node가 있다. 따라서 각 요소에는 다음 요소로 접근할 주소를 갖고 있는 것이다. (마치 쇠사슬같이 연결된 구조)
Array와 LinkedList는 이러한 데이터 구조의 차이로 인하여 다음과 같은 차이점이 발생한다.
- 요소에 대한 접근은 Array가 LinkedList 보다 유리하다.
기존의 배열은 index만 알면 요소에 대한 접근이 쉽지만, LinkedList는 각 요소가 다음 요소로 접근할 수 있는 주소를 가지고 있기 때문에 해당요소로 접근하기까지 필요한 요소들을 하나하나 전부 거친 후 접근하여야 한다. 따라서 Array는 RandomAccessing이 가능하다고 표현한다.
- 중간 요소의 삭제, 추가는 LinkedList 가 Array 보다 유리하다.
Array는 배열의 크기를 변경할 수 없다고 했다. 따라서 요소를 삭제, 추가하면 크기가 달라지는데 이때 아예 새로운 배열(새로운 주소 값)을 만들어서 복사를 해야 하기 때문에 시간을 많이 잡아먹는다.
하지만 LinkedList는 node의 연결이기 때문에 이 연결만 바꾸어 주면 삭제, 추가가 끝난다. 연결을 바꾸어 준다는 것은 node에 담긴 다음 요소로 가는 주소 값을 변경하는 것이다.
Array는 정적 배열로써 한번 선언하면 그 크기를 바꿀 수 없기 때문에 데이터의 개수가 변하지 않고 순차적으로 삭제, 추가를 해야 할 경우엔 효율적이다. 또한 index를 안다면 요소에 대한 접근이 빠르다. 다만 중간요소의 삭제,추가가 잦은 데이터구조에는 사용하지 않는게 좋다.
LinkedList는 node를 이용하여 다음 요소로 접근하는 방식 덕분에 데이터의 삭제, 추가가 편리하고, 이로 인하여 새로운 데이터의 추가나 삭제시 용량도 변화하기 때문에 데이터개수의 변경이 잦을때 효율적이다. 하지만 요소에 접근하는 데 있어서 시간이 오래 걸리고, 데이터가 많아진다면 접근시간이 더 오래 걸린다는 단점이 있다.
'Java > Java Study' 카테고리의 다른 글
| [Collections Framework] Arrays (0) | 2021.06.03 |
|---|---|
| [객체지향] Static 메서드는 언제 쓸까? (0) | 2021.06.02 |
| [Collections Framework] Iterator 와 메서드 iterator (0) | 2021.05.27 |
| [Collections Framework] ArrayList (0) | 2021.05.27 |
| [Collections Framework] 컬렉션 프레임워크란? (0) | 2021.05.24 |