[List] LikedList

LikedList 등장 ?

기존에 배열은 구조가 간단하며 연결되어 있기에 조회 속도가 빠르다는 장점이 있다. 그러나 상황에 따른 다음과 같은 단점이 존재한다.

1. 배열은 크기가 고정되면 변경할 수 없다.
2. 비순차적인 위치 데이터를 삭제/추가하려면 배열 안에 요소들의 이동이 발생한다.

LikedList는 Array에 이와같은 단점을 보완하기 위하여 나왔다.

 

LikedList란 ?

LikedList는 객체를 사용하여 내부적으로 값과 다음 객체의 주소를 갖고 있기에 실제로  물리적인 연결이  아닌 주소 값을 참조함으로 논리적인 연결형태의 List형 자료구조이다. 이와같은 LikedList에서 데이터를 추가/삭제하기 위해서는 데이터의 순서에 따른 객체 사이의 참조를 변경함으로 비순서적인 데이터 추가 / 삭제에 유연하게 대처할 수 있다. 

 

그러나 LinkedList는 단방향성이기에 이전 요소로 이동하지는 못한다. 그래서 이러한 점을 보완하기 위해서  doubly linked list(=이중  연결 리스트)가 나왔으며 이전 요소에 대한 참조를 추가적으로 갖고 있어 양방향성을 갖으며 실제로 ListkedList는 더블 링크드 리스트로 되어있다.

 

추가적으로 더블 링크드 리스트에서 양 끝을 서로 연결하여 순환형태를 갖는 이중 원형 연결리스트도 있다.

 

LikedList 기능 ?

👆👆👆👆👆

정말 많은 기능들이 있다 이러한 부분들은 LinkedList Class를 보면  Deque(Queue), List 인터페이스를 구현한 것인데 그에따라서 사용할 수 있는 메서드명을 보면 이 두가지가 함께 사용할 수 있는 메서드로 있는 것을 볼 수 있었다.

 

LikedList / ArrayList 성능 비교 ?

public static void main(String[] args) {
        ArrayList al = new ArrayList(2000000);
        LinkedList ll = new LinkedList();

        System.out.println("= 순차적으로 추가하기 =");
        System.out.println("ArrayList : " + add1(al));
        System.out.println("LikedList : " + add1(ll));
        System.out.println();
        System.out.println("= 중간에서 추가하기 =");
        System.out.println("ArrayList : " + add2(al));
        System.out.println("LikedList : " + add2(ll));
        System.out.println();
        System.out.println("= 중간에서 삭제하기 =");
        System.out.println("ArrayList : " + remove2(al));
        System.out.println("LikedList : " + remove2(ll));
        System.out.println();
        System.out.println("= 순차적으로 삭제하기 =");
        System.out.println("ArrayList : " + remove1(al));
        System.out.println("LikedList : " + remove1(ll));
        System.out.println();

}

/* 출력결과
= 순차적으로 추가하기 =
ArrayList : 250
LikedList : 449

= 중간에서 추가하기 =
ArrayList : 5500
LikedList : 22

= 중간에서 삭제하기 =
ArrayList : 3716
LikedList : 183

= 순차적으로 삭제하기 =
ArrayList : 16
LikedList : 52
*/

 

컬렉션	읽기(접근시간)	추가 / 삭제	내용
ArrayList	상대적으로 빠름	느리다	순차적으로 추가/삭제 시 빠름 비효율적인 메모리사용
LinkedList	상대적으로 느림	빠르다	데이터가 많을수록 접근성이 떨어짐

👆👆👆👆👆

둘 다 순서는 보장하지만 컬렉션을 다루면서 주로 발생하는 문제들에 대해서 고려하고 상황에 맞는 자료구조를 사용하자!!!

 

LikedList / ArrayList 형변환 ?

ArrayList al = new ArrayList(1000);
for(int i = 0 ; i < 10 ;i++) al.add(i+"");
LinkedList ll = new LinkedList(al);
al = new ArrayList(ll);

//LinkedList 생성자
public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
}

//ArrayList 생성자
public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

👆👆👆👆👆

collectionFramwork에 속한 대부분의 컬렉션 클래스들은 이처럼 서로 변환이 가능한 생성자를 제공한다.