LinkedList란

배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어 오는데 걸리는 시간(접근시간)이 빠르다는 장점이 있다 하지만 크기를 변경하는데 메모리 소비가 크고 배열 중간에 데이터를 추가하거나 삭제할 때 소모되는 값이 크다는 단점을 가진다. 이러한 단점을 보완하기 위해 고안된 자료구조가 LinkedList이다.

배열과 LinkedList를 비교한 그림이다. 배열은 자신의 값만 알고 있다. 그에 반해 LinkedList는 자신의 값과 자신의 다음 배열에 대한 주소값을 같이 갖고 있다. 이렇게 됐을 때의 장점은 여기서 중간의 삭제가 일어나거나 추가가 일어나면 다음 배열의 주소값만 변경하면 된다는 것이다.

예를 들어 위 그림과 같이 원래의 LinkedList에서 4번째 인덱스가 삭제되었을 때 3번째 인덱스의 다음 노드의 주소값이 다음과 같이 변경됨을 확인할 수 있다. 추가 또한 마찬가지이다.

하지만 이런 LinkedList에도 단점이 또 존재하는데 현재의 LinkedList는 단방향으로만 이동할 수 있다는 것이다. 자신의 다음 노드에 대한 정보만 있기 때문에 이전 노드를 접근하기에는 어려움이 있다. 그래서 이 점을 보완하기 위해 더블 링크드 리스트라는 개념이 고안되었다.

Doubly Linked List

더블 링크드 리스트는 단순히 링크드 리스트에 참조변수를 하나 더 추가해주는 개념이다.

class Node{
    Node next;		//다음 요소의 주소 저장
    Object object	//데이터 저장
}

링크드 리스트

class Node{
    Node next;		//다음 요소의 주소 저장
    Node previous;	//이전 요소의 주소 저장
    Object object	//데이터 저장
}

더블 링크드 리스트

이를 그림으로 더 자세히 확인해보자.

다음과 같이 하나의 참조변수가 더 추가된 그림이다. 이렇게 되면 이전의 주소도 갖고 있어서 이전 데이터로 접근이 편해졌다. 그리고 이보다 좀 더 접근성을 향상 시킨 doubly circular linked list의 개념이 존재하는데

위의 더블 링크드 리스트와 더블 서큘러 링크드 리스트의 차이점을 색으로 표시해놨다. 이렇게 되면 각 배열의 끝에서도 이전과 다음 값을 검색할 수 있게 되었는데. 이를 실생활에서 사용하고 있는 예시로 TV 채널을 생각하면 적당하다. 티비의 가장 처음 채널에서 채널을 감소 시키면 채널의 가장 마지막 채널이 나오고 마지막 채널에서 증가시키면 처음 채널이 나오는 현상과 같다.

대체로 우리가 LinkedList로 사용하는 개념은 더블 링크드 리스트라고 생각하면 된다.

ArrayList와 LinkedList

지금까지 글을 보면 ArrayList와 배열보다 LinkedList가 훨씬 좋아보이는데 왜 LinkedList를 무조건 사용하지 않고 상황에 따라서 ArrayList를 사용하고 어떨때는 LinkedList를 사용할까?

ArrayList의 배열의 메모리 구조는

인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

와 같이 생성된다. 여기서 추가되어지고 삭제되어져도 배열의 주소는 동일하며 값만 변경되므로 만약 리스트를 탐색하게 된다면 그저 주소값으로 바로 가져올 수 있다. 이에 반면 LinkedList는

다음과 같이 중간에 값이 삭제되고 추가되었다면 연속된 주소값이 아닌 각각의 다른 주소값을 가지게 된다. 그래서 인덱스 정보만으로 주소값을 찾을 수가 없기 때문에 0부터 차례대로 검색하여 해당 인덱스까지 탐색하게된다.

그래서 LinkedList는 저장해야하는 데이터의 개수가 많아질수록 데이터를 읽어 오는데 접근시간이 길어진다는 단점이 있다.

각 리스트를 정리하면 다음과 같으며 이를 통해 다루고자 하는 데이터의 개수가 변하지 않는 경우라면 ArrayList를 선택, 데이터가 계속해서 변경된다면 LinkedList를 선택하는게 더 나은 선택이 될 수 있다.

내가 몰랐던 LinkedList의 메서드

int lastIndexOf(Object o) 지정된 객체의 위치를 반환(끝에서 역순으로 검색하여 반환함)
Object poll() 첫번째 요소를 반환, 반환된 요소는 LinkedList에서 제거
void addFirst(Object o) 리스트 맨 앞에 추가
Iterator descendingIterator() Iterator의 내용을 역순으로 반환
Obejct getFirst() 첫번째 요소 반환
Obejct getLast() 마지막 요소 반환
boolean removeFirstOccurrence(Object o) 리스트에서 첫번째로 일치하는 객체 제거