[자바] LinkedList

배열은 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간이 가장 빠르다는 장점을 가지고 있지만, 단점도 있다.

---

1. 크기를 변경할 수 없다.

- 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야 한다.

- 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다.

2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

- 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는것은 빠르지만 배열의 중간에 데이터를 추가하려면 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 한다.

---

이러한 배열의 단점을 보완하기 위해서 링크드 리스트(linked list) 라는 자료구조가 고안되었다.

배열은 데이터가 연속적으로 존재하지만 linked list는 데이터를 서로 연결(link)한 형태로 구성되어 있다.

linked list에서의 데이터 삭제는 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다. 배열처럼 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다.

추가할 때 역시 마찬가지로 이전요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면되므로 추가 역시 처리속도가 매우 빠르다.

linked list는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만, 이전요소에 대한 접근은 어렵다. 이 점을 보완한 것이 이중 연결 리스트(doubly linked list, 더블 링크드 리스트)이다.

더블 링크드 리스트의 접근성을 보다 향상시킨 것이 더블 서큘러 링크드 리스트(이중 원형 연결 리스트, doubly circular linked list)인데, 더블 링크드 리스트의 첫 번째 요소와 마지막 요소를 서로 연결시켰다.

실제로 LinkedList클래스는 이름과 다르게 링크드 리스트가 아닌 더블 링크드 리스트로 구현되었다.

이러한 다양한 이유로 개인적으로는 프로젝트할 때 ArrayList 보다는 Linked List를 더 많이 사용했다.

생성자 또는 메서드	설 명
LinkedList()	LinkedList 객체를 생성
LinkedList(Collection c)	주어진 컬렉션을 포함하는 LinkedList 객체를 생성
boolean add(Object o)	지정된 객체(o)를 LinkedList의 끝에 추가, 저장에 성공하면 true, 실패하면 flalse
void add(int index, Ojbect element)	지정된 위치(index)에 객체(element)를 추가
boolean addAll(Collection c)	주어진 컬렉션에 포함된 모든 요소를 LinkedList의 끝에 추가한다. 성공하면 true, 실패하면 false
boolean addAll(int index, Collection c)	지정된 위치(index)에 주어진 컬렉션에 포함된 모드 요소를 추가. 성공하면 true, 실패하면 false
void clear()	LinkedList 의 모든 요소를 삭제
boolean contains(Object o)	지정된 객체가 LinkedList에 포함되어 있는지 알려준다.
boolean containsAll(Collection c)	지정된 컬렉션의 모든 요소가 포함되어 있는지 알려준다.
Object get(int index)	지정된 위치(index)의 객체를 반환
int indexOf(Object o)	지정된 객체가 저장된 위치(앞에서 몇 번째)를 반환
boolean isEmpty()	LinkedList가 비어있는지 알려준다. 비어있으면 true
Iterator iterator()	Iterator 를 반환한다.
int lastIndexOf(Obejct o)	지정된 객체의 위치를 반환(끝부터 역순검색)
ListIterator listIterator()	ListIterator를 반환
ListIterator ListIterator(int index)	지정된 위치에서부터 시작하는 ListIterator를 반환
Object remove(int index)	지정된 위치의 개체를 LinkedList에서 제거
boolean remove(Ojbect o)	지정된 객체를 LinkedList에서 제거, 성공하면 true, 실패하면 false
boolean removeAll(Collection c)	지정된 컬렉션의 요소와 일치하는 요소를 모두 삭제
boolean retainAll(Collection c)	지정된 컬렉션의 모든 요소가 포함되어 있는지 확인
Object set(int index, Object element)	지정된 위치(index)의 객체를 주어진 객체로 바꿈
int size()	LinkedList에 저장된 객체의 수를 반환
List subList(int fromIndex, int toIndx)	LinkedList의 일부를 List로 반환
Object[] toArray()	LinkedList에 저장된 객체를 배열로 반환
Object[] toAraay(Object[] a)	LinkedList에 저장된 객체를 주어진 배열에 저장하여 반환
Object element()	LinkedList에 첫 번째 요소를 반환
boolean offer(Object o)	지정된 객체(o)를 LinkedList의 끝에 추가. 성공하면 true, 실패하면 false
Object peek()	LinkedList의 첫 번째 요소를 반환
Object poll()	LinkedList의 첫 번째 요소를 반환, LinkedList에서는 제거
Object remove()	LinkedList의 첫 번째 요소를 제거
void addFirst(Object o)	LinkedList의 맨 앞에 객체(o)를 추가
void addLast(Object o)	LinkedList의 맨 끝에 객체(o)를 추가
Iterator descendingIterator()	역순으로 조회하기 위한 DescendingIterator를 반환
Object getFirst()	LinkedList의 첫번째 요소를 반환
Object getLast()	LinkedList의 마지막 요소를 반환
boolean offerFirst(Object o)	LinkedList의 맨 앞에 객체(o)를 추가, 성공하면 true
booelan offerLast(Object o)	LinkedList의 맨 끝에 객체(o)를 추가, 성공하면 true
Object peekFirst()	LinkedList의 첫번째 요소를 반환
Object peekLast()	LinkedList의 마지막 요소를 반환
Ojbect pollFirst()	LinkedList의 첫번째 요소를 반환하면서 제거
Object pollLast()	LinkedList의 마지막 요소를 반환하면서 제거
Object pop()	removeFirst()와 동일
void push(Object o)	addFirst()와 동일
Object removeFirst()	LinkedList의 첫번째 요소를 제거
Object removeLast()	LinkedList의 마지막 요소를 제거
boolean removeFirstOccurrence(Object o)	LinkedList에서 첫번째로 일치하는 객체를 제거
boolean removeLastOccurrence(Object o)	LinkedList에서 마지막으로 일치하는 객체를 제거

LinkedList 역시 List 인터페이스를 구현했기 때문에 ArrayList와 내부구현방법만 다를뿐 제공하는 메서드의 종류와 기능은 거의 같다.

import java.util.*;

public class ArrayListLinkedListTest {

    public static void main(String[] args) {

        ArrayList al = new ArrayList(2000000);
        LinkedList ll = new LinkedList();

        System.out.println("순차 추가");
        System.out.println("ArrayList:" + add_1(al));
        System.out.println("LinkedList:" + add_1(ll));

        System.out.println("==================");

        System.out.println("중간에 추가");
        System.out.println("ArrayList:" + add_2(al));
        System.out.println("LinkedList:" + add_2(ll));

        System.out.println("==================");

        System.out.println("순차적으로 삭제");
        System.out.println("ArrayList:" + remove_1(al));
        System.out.println("LinkedList:" + remove_1(ll));

        System.out.println("==================");

        System.out.println("중간 삭제");
        System.out.println("ArrayList:" + remove_2(al));
        System.out.println("LinkedList:" + remove_2(ll));

    }

    public static long add_1(List list) {

        long start = System.currentTimeMillis();

        for (int i = 0; i < 1000000; i++) {
            list.add(i);
        }

        long end = System.currentTimeMillis();

        return end - start;
    }

    public static long add_2(List list) {

        long start = System.currentTimeMillis();

        for (int i = 0; i < 1000000; i++) {
            list.add(500, "X");
        }

        long end = System.currentTimeMillis();

        return end - start;
    }

    public static long remove_1(List list) {

        long start = System.currentTimeMillis();

        for (int i = list.size() - 1; i >= 0; i--) {
            list.remove(i);
        }

        long end = System.currentTimeMillis();

        return end - start;
    }

    public static long remove_2(List list) {

        long start = System.currentTimeMillis();

        for (int i = 0; i < list.size(); i++) {
            list.remove(i);
        }

        long end = System.currentTimeMillis();

        return end - start;
    }

}

실행결과

순차 추가
ArrayList:24
LinkedList:100
==================
중간에 추가
ArrayList:336414
LinkedList:931
==================
순차적으로 삭제
ArrayList:108
LinkedList:30
==================
중간 삭제
ArrayList:0
LinkedList:0

결과를 보면 순차로 추가하는건 ArrayList가 시간이 적게 걸리고 중간에 추가하는건 LinkedList가 압도적으로 적게 걸린다.
위 소스의 경우는 ArrayList의 크기가 충분히 확보돼서 새로운 크기의 ArrayList를 생성하고 데이터를 복사하는 일이 발생하지 않았기 때문에 만약 ArrayList의 초반 크기를 여유있게 확보하지 못 한 상황이라면 순차 추가 역시 LinkedList가 더 빠를 수 있다.

중간에 추가하는경우 LinkedList는 각 요소간의 연결만 변경해주면 되기 때문에 ArrayList랑 비교했을 때 속도가 엄청나게 빠르다.
ArrayList는 요소들을 재배치하여 추가 할 공간을 확보하거나 빈 공간을 채워나가다보니 처리속도가 늦다.

데이터수가 적다면 ArrayList와 LinkedList 를 비교테스트해봤을 때 별 차이가 없다.

조회시에는 배열은 요소들이 연속적으로 메모리상에 존재하기 때문에 원하는 요소의 주소를 얻어서 저장된 데이터를 곧바로 읽어올 수 있지만, linkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야 원하는 값을 얻을 수 있다.

그래서 linkedList는 저장해야하는 데이터가 갯수가 많아질수록 데이터를 읽어오는 시간은 길어진다는 단점이 있다.

컬렉션	읽기(접근시간)	추가/삭제	비고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠름. (크기가 여유있게 지정됐을 때) 비효율적인 메모리 사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐.

다루고자 하는 데이터의 갯수가 변하지 않는 경우라면 ArrayList가 좋은 선택이 될 수 있고, 데이터 갯수의 변경이 잦다면 LinkedArray 사용이 더 나을 수도 있다.
또는 두 클래스를 조합해서 사용하는것도 좋은 방법이 될 수 있다.

 

 

참고: 자바의정석