컬렉션 List - LinkedList

연결리스트(LinkedList)의 등장 배경

기존의 ArrayList의 경우 이전 글에서 언급했듯이 단점이 존재한다.

 

우선 배열이 확장될 때마다 새로운 배열을 생성해서 복사하는 과정을 지속한다.

 

그렇다보니 실행 속도에서 손해를 본다. 만약 배열 크기를 미리 크게 잡으면 메모리 낭비가 생긴다.

 

또한 배열의 중간 데이터를 추가, 삭제할 경우 데이터 이동이 일어나 실행 시간이 오래 걸린다.

 

ArrayList는 배열을 기반으로 하다보니 ArrayList 또한 배열의 단점을 그대로 가져간다.

 

이러한 ArrayList의 단점을 보완하는것이 연결리스트(LinkedList)다.

연결리스트(LinkedList)란?

연결리스트란 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성된 리스트를 말한다.

 

이렇게 들으면 좀 이상한데 아래 그림을 보면 이해가 더 쉬울 것이다.

 

 

 

기존의 배열은 배열을 선언하게 되면 모든 데이터가 연속적으로 존재한다.

 

반면 연결리스트는 각 요소가 데이터 + 다음 요소에 대한 참조(주소값)으로 이뤄진다.

 

참고로 이때 각 요소를 노드(Node)라고 부른다.

 

즉 각 요소는 다음 요소를 가리키는 주소를 가지게 된다.

연결리스트(Linked List)의 장점

연결리스트가 ArrayList에 비해 가지는 장점은 확실하다.

 

배열 중간에 있는 요소를 추가, 삭제할 때 속도가 더 빠르다.

 

 

 

위 그림을 보자.

 

ArrayList에서는 중간에 있는 요소를 삭제한다고 할 때 삭제 요소 뒤의 모든 요소를 앞으로 당겨야한다.

 

예시에선 요소가 3개뿐이라 별거 아닌 것 같지만 수많은 요소가 있으면 그만큼 처리 시간이 길어진다.

 

 

 

 

반면에 연결리스트는 다르다.

 

중간 요소가 삭제될 경우 요소를 삭제하면서 삭제되는 요소 이전에 위치한 요소가 가진 참조만 변경해준다.

 

연결리스트는 각 요소가 따로 다음 요소에 대한 참조값을 가지므로 이것만 수정해주면 되는 것이다.

 

 

 

 

배열 중간에 새로운 요소를 추가하는 경우도 ArrayList에 비해 월등히 속도가 빠르다.

 

ArrayList는 중간에 새로운 요소를 추가해줄 경우 새로 추가해준 요소 뒤의 요소는 뒤로 한칸씩 밀린다.

 

반면 연결리스트는 새로운 요소를 생성하면서 추가하고자 하는 위치 다음 주소값을 부여한다.

 

그리고 추가하고자 하는 위치 이전 요소의 주소값은 새로 추가된 요소의 주소값으로 갱신해주면 된다.

 

설명이 난해하면 그림을 자세히보면 이해가 더 쉬울 것이다.

 

정리하자면 연결리스트는 새로운 요소를 추가, 삭제하는데 있어서 ArrayList에 비해 큰 장점을 갖는다.

연결리스트의 단점

하지만 이런 연결리스트도 단점이 있다.

 

요소 별로 데이터와 함께 다음 주소에 대한 주소값만 가지고 있다는 것이다.

 

 

위 그림을 보면 알겠지만 연결리스트는 빨간 화살표 방향으로 단방향 이동을 한다.

 

즉 다음 요소에 대한 접근은 쉽지만, 이전 요소에 대한 접근은 어렵다는 것이다.

 

이러한 단점을 보완하고자 나온 것이 이중 연결 리스트(doubly linked list)다.

이중 연결 리스트와 이중 원형 연결 리스트

이중 연결 리스트(doubly linked list)는 기존 연결리스트(linked list)의 단점을 보완하고자 나왔다.

 

기존의 연결리스트의 각 요소가 데이터+다음 요소에 대한 주소값을 가졌다면,

 

 

이중 연결 리스트는 각 요소가 데이터+다음 요소에 대한 주소값+이전 요소에 대한 주소값을 가진다.

 

위 그림을 보면 더 쉽게 이해가 가능할 것이다.

 

기존 연결 리스트가 다음 요소에 대한 주소값만 가지고 있어서 단방향으로 움직일 수 있었다면,

 

이중 연결 리스트는 이전, 다음 요소에 대한 주소값을 모두 가지고 있어 양방향으로 움직일 수 있다.

 

실제로 LinkedList 클래스는 이름과 달리 연결리스트가 아니라 이중연결리스트를 구현한다.

 

이유는 기본적인 연결리스트는 단점이 많고 사용이 불편하기 때문이다.

 

그래서 우리가 실제로 LinkedList를 이용할 때는 이중연결리스트를 쓰는 것과 같다고 봐야 한다.

 

하지만 이러한 이중 연결 리스트도 단점은 존재한다.

 

바로 맨 처음과 맨 끝 요소가 유기적으로 연결되지 않는다는 것이다.

 

그림에서 보듯 맨 처음 요소와 맨 끝의 요소는 각각 null을 하나씩 가지고 있다.

 

그렇기 때문에 끝 요소에서 첫 요소로 돌아가기 위해서는 모든 요소를 다 거쳐서 먼 거리를 가야한다.

 

그래서 등장한 것이 이중 원형 연결리스트(doubly circular linked list)다.

 

 

이중 원형 연결리스트는 위 그림처럼 작동한다.

 

기존의 이중 연결 리스트가 맨 앞 요소는 다음 요소의 주소값만,

 

맨 뒤의 요소는 이전 요소의 주소값만 가진 것에 비해,

 

이중 원형 연결 리스트는 맨 앞 요소는 맨 끝 요소의 주소,

 

다음 요소의 주소값을 갖고 맨 뒤 요소는 맨 앞 요소의 주소, 이전 요소의 주소값을 갖는다.

 

즉 맨 앞과 맨 뒤 요소를 연결해줌으로써 리스트 내에서 양방향과 유기적으로 순환할 수 있게 된다.

 

표로 정리하면 다음과 같다.

 

Linked List	본인의 데이터값, 다음 요소에 대한 주소값
Doubly Linked List	본인의 데이터값, 다음 요소 주소값, 이전 요소 주소값
Doubly Circular Linked List	본인의 데이터값, 다음 요소 주소값, 이전 요소 주소 + 첫번째 요소는 마지막 요소 주소값 포함 마지막 요소는 첫번째 요소 주소값 포함

연결리스트(LinkedList) 사용법

연결리스트도 List 인터페이스를 상속받았으므로 ArrayList와 기본 사용법은 같다.

 

하지만 연결리스트만의 특성 덕분에 몇 가지 고유 메서드가 있다.

 

 

    public static void main(String[] args) {

        // LinkedList는 미리 크기를 설정하지 않고 선언한다.
        LinkedList test_1 = new LinkedList();

        // LinkedList는 List 인터페이스를 확장했으므로
        // List자료형으로도 사용이 가능하다.
        List test_2 = new LinkedList();

        // add(): 리스트에 데이터를 추가
        test_1.add("b");
        test_1.add("c");
        test_1.add("d");

        // get(): 저장된 객체 반환(데이터 조회 및 조작)
        test_1.get(0);

        // peek(): 리스트의 첫번째 요소를 반환
        test_1.peek();

        // getFirst(): 리스트의 첫번째 요소를 반환
        // getLast(): 리스트의 마지막 요소를 반환
        test_1.getFirst();
        test_1.getLast();

        // addFirst(): 리스트의 맨 앞에 객체를 추가
        // addLast(): 리스트의 맨 뒤에 객체를 추가
        test_1.addFirst("a");
        test_1.addLast("e");

        // contatins(): 리스트 내 괄호 안 데이터가 있는지 확인
        test_1.contains("a");

        // indexOf(): 리스트 내 괄호 안 데이터가 위치한 인덱스 반환
        test_1.indexOf("a");

        // size(): 리스트 내 데이터 개수를 반환
        test_1.size();

        // remove(): 괄호 안 인덱스에 위치한 데이터 삭제
        test_1.remove(0);

        // remove(): 리스트 내에 괄호 안 데이터와 동일한 데이터 삭제
        test_1.remove("a");

        // clear(): 리스트를 완전히 비운다.
        test_1.clear();

        // isEmpty(): 리스트가 비어있는지 확인
        test_1.isEmpty();

    }

LinkedList와 ArrayList

이전 포스트와 이번 포스트에서 LinkedList와 ArrayList에 대해서 알아봤다.

 

둘은 비슷한 부분도 많지만 분명한 차이점이 있다.

 

그럼 과연 어떨 때 어떤 List를 사용해야 적절할까?

 

우선 결론부터 말하면 다루는 데이터 양이 적으면 둘 다 큰 차이가 없다.

 

하지만 데이터가 많아질 경우에는 상황에 따라 선택 기준이 달라진다.

 

상황	설명
데이터를 순차적으로 추가/삭제하는 경우	ArrayList의 초기 저장 공간을 여유있게 잡았다는 전제하에 데이터를 순차적으로 추가, 삭제하는 경우는 ArrayList가 유리하다 다만 초기 저장 공간이 여유가 없다면 ArrayList는 배열이 확장될 때마다 새로울 배열 생성 및 복사가 발생하므로 Linked에 비해 불리할 수 있다.
중간에 데이터를 추가/삭제하는 경우	리스트의 중간 요소들을 자주 추가, 삭제하는 경우 LinkedList가 유리하다. 위의 설명에서도 말했듯 LinkedList는 중간 요소를 추가 삭제해도 나머지 요소의 정렬이 필요없으므로 속도면에서 굉장히 유리하다.
많은 데이터를 조회해야 하는 경우	많은 양의 데이터를 조회해야 할 경우 ArrayList가 유리하다. ArrayList의 각 요소들은 메모리 상에 연속적으로 존재한다. 반면 LinkedList의 각 요소들은 메모리 상에 비연속적으로 존재한다. 그래서 많은 양의 데이터를 조회하는건 당연히 ArrayList가 유리하다.

 

간단히 정리하자면 다루는 데이터의 개수가 변하지 않으면 ArrayList가 유리하다.

 

반면 데이터의 개수가 자주 변한다면 LinkedList를 사용하는 것이 나은 선택이다.