[Java] LinkedList

1.  LinkedList (링크드리스트)

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

• 크기를 변경할 수 없다. - 크기를 변경할 수 없으므로 새로운 배열을 생성해 데이터를 복사해야한다.
• 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다. - 차례대로 데이터를 추가하고 , 마지막부터 삭제하는 것은 빠르지만, 배열의 중간에 데이터를 추가하려면 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야한다.

이러한 배열의 단점을 보완하기 위해서 LinkedList라는 자료구조 형태가 나왔다. 링크드리스트는 메모리상에서 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어있다.

링크드리스트의 각 요소(Node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)과 데이터로 구성되어 있다.

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

링크드 리스트의 삭제는 간단한데. 삭제하고자하는 요소의 이전요소가 삭제하고자하는 요소의 다음 요소를 참조하다록만 변경하면 된다. 새로운 데이터를 추가할 때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소로 참조로 변경하고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 된다.

참고로 Linkedlist는 ArrayList와 달리 인덱스가 존재하지 않는다. 따라서 순차탐색이 필요하다.

더블 링크드 리스트

하지만, 이런 링크드 리스트 이동방향이 단방향이기때문에 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접은은 어렵다. 예를들어 링크드 리스트에 저장된 데이터가 10000개라면 9999번째 데이터에 접근하려면 9999번 이동해야한다. 이러한 단점을 해결한것이 **더블 링크드 리스트 (이중 연결리스트, doubly linked list)**이다. 링크스 리스트에 참조변수를 하나 더 추가해 다음 요소에 대한 참조뿐만이 아니라 이전 요소에 대한 참조가 가능하도록 했다.

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

더블 써큘러 링크드 리스트

더블 링크르 리스트의 접근성을 보다 향상시킨 것이 더블 서큘러 링크드 리스트(이중 원형 연결리스트, doubly circular linked list)이다. 단순히 더블 링크드 리스트의 첫번째와 마지막 요소를 서로 연결시킨 것이다. 따라서 마지막 요소의 다음 요소가 첫번째 요소가 되고, 첫번째 요소의 이전 요소가 마지막 요소가 된다. 따라서 링크드리스트에 저장된 데이터가 10000개 일때 9999번째 데이터에 접근하기 위해 9999번째를 이동하지 않아도 된다.

실제로 자바의 LinkedList의 클래스는 링크드리스트라는 이름이 아닌 더블링크드리스트로 구현되어 있다.

메서드 설명

메서드	설명
LinkedList()	LinkedList 객체 생성
LinkedList(Collection c)	주어진 컬렉션을 포함하는 LinkedList 객체를 생성
boolean add(Object o)	지정된 객체(o)를 LinkedList의 끝에 추가. 저장에 성공하면 true, 실패하면 false
void add(int index, Object element)	지정된 index에 객체를 추가
boolean addAll(Collection c)	주어진 컬렉션에 포함된 모든 요소를 LinkedList의 끝에 추가한다.
boolean addAll(int index, Collection c)	지정된 위치에 주어진 컬렉션에 포함된 모든 요소를 추가한다.
void clear()	LinkedList안에 모든 요소를 삭제한다.
boolean contains(Object o)	지정된 객체가 lInkedList에 포함되었는지 알려준다.
boolean containsAll(Collection c)	지정된 컬렉션의 모든 요소가 포함되었는지 확인한다.
Object get(int index)	index로 객체를 반환한다.
index를 통한 get 매소드를 제공하지만 실제로는 순차탐색으로 이루어져있다.
int indexOf(Object o)	지정된 객체가 저장된 위치를 반환한다.
boolean isEmpty()	LinkedList가 비어있는지 알려준다.
Iterator Iterartor()	Iterator를 반환한다.
int lastIndexOf(Object o)	지정된 객체가 저장된 위치를 끝부터 검색해 반환한다.
ListIterator listIterator()	ListIterator를 반환한다.
ListIterator listIterator(int index)	지정된 위치에서부터 시작하는 ListIterator를 반환한다.
Object remove(int index)	지정된 위치의 객체를 LinkedList에서 제거한다.
boolean remove(Object o)	지정된 객체를 linkedList에서 제거한다.
boolean removeAll(Collection c)	지정된 컬렉션의 요소와 일치하는 요소를 모두 삭제
boolean retainAll(Collection c)	지정된 컬렉션의 모든 요소가 포함되어있는지 확인
Object set(int index, Object element)	지정된 위치의 객체를 주어진 객체로 바꾼다.
int size()	LinkedList의 저장된 객체 수를 반환
List subList(int fromIndex, int toIndex)	LinkedList의 일부를 List로 반환
Object[] toArray()	LinkedList에 저장된 객체를 배열로 반환
Object[] toArray(Object[] a)	LinkedList에 저장된 객체를 주어진 배열에 저장해 반환
Object element()	LinkedList의 첫번째 요소를 반환
boolean offer(Object o)	지정된 객체(o)를 lInkedList의 끝에 추가.
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를 추가
boolean offerLast(Object o)	LinkedList의 맨 끝에 객체 o를 추가
Object peekFirst()	LinkedList의 첫번째 요소를 반환
Object peekLast()	LinkedList의 마지막 요소를 반환
Object pollFirst()	LinkedList의 첫번째 요소를 반환하면서 동시에 제거
Object pollLast()	LinkedList의 마지막 요소를 반환하면서 동시에 제거
Object pop()	removeFirst() 와 동일. 첫번째 요소를 제거
void push(Object o)	addFirst()와 동일. 맨 앞에 객체 o를 추가
Object removeFirst()	LinkedList의 첫번째 요소를 제거
Object removeLast()	LinkedList의 마지막 요소를 제거
boolean removeFirstOccurrence(Object o)	첫번째로 일치하는 객체를 제거
boolean removeLastOccurrence(Object o)	마지막으로 일치하는 객체를 제거

//링크드 리스트 객체 생성
LinkedList<String> l1 =  new LinkedList<>();
l1.add("A"); // ["A"]

//주어진 컬렉션을 포함하는 LinkedList 객체 생성
LinkedList<String> l2 = new LinkedList<>(l1); //["A"]

(참고로 LinkedList는 Queue 인터페이스와 Deque 인터페이스를 구현하도록 변경되었는데, 마지막 22개의 메소드는 Queue 인터페이스와 Deque 인터페이스를 구현하면서 추가된 것이다. )

 

ArrayList와 Array를 비교한다면

1. 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다. ArrayList를 처음 생성할때 저장할 데이터의 개수만큼 충분한 초기용량을 확보한상태라면 저장공간이 부족해서 새로운 ArrayList를 만들고 복사하는 일을 발생하지 않기 때문에 순차적으로 데이터를 추가한다면 LinkedList보다 Arraylist가 더 빠르다. 또한 데이터를 순차적으로 삭제한다는 것은 마지막 데이터부터 역순으로 삭제해나간다는 것을 의미하므로 ArrayList는 마지막 데이터부터 삭제할경우 요소들의 재배치가 필요하지 않기 때문에 상당히 빠른다. 단지 마지막 요소의 값을 null로만 바꾸면 되니까.
2. 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다. 중간 요소를 추가,삭제하는 경우 LInkedList는 각 요소간의 연결만 변경해주면 되므로 처리속도가 빠르다. 하지만 ArrayList는 요소를 재배치해 공간을 확보 또는 빈 공간을 채워야하기때문에 처리속도가 늦다.

public class ArrayListLinkedListTest {
    public static void main(String[] args) {
        //생성
        ArrayList<Object> a1 = new ArrayList<>(1000000);
        LinkedList<Object> l1 = new LinkedList<>();

        //데이터 추가
        add(a1);
        add(l1);

        System.out.println("= 접근시간테스트 ==");
        System.out.println("ArrayList: " + access(a1)); //1
        System.out.println("LinkedList: " + access(l1));//317
    }

    public static void add(List list) {
        for (int i = 0; i < 1000000; i++) {
            list.add(i + "");
        }
    }

    public static long access(List list) {
        long start = System.currentTimeMillis(); //현재시각을 밀리세컨드 단위로 반환
        for (int i = 0; i < 10000; i++) {
            list.get(i);
        }
        long end = System.currentTimeMillis();
        return end - start; //걸리는 시간
    }
}

ArrayList와 LinkedList의 접근시간테스트를 해보면 Arraylist가 LinkedList보다 현저히 빠르다. 그 이유는 배열의 경우 만일 인덱스가 n인 요소의 값을 얻어 오고자 한다면 단순히 아래와 같은 수식을 계산함으로써 해결한다

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

Object[] arr = new Object[5];
//arr[2]의 주소? 

Object배열 arr 이 선언되었을 때 arr[2]에 저장된 값을 읽으려 한다면 n은 2 , 모든 참조형 변수의 크기는 4byte , 생성된 배열의 주소는 ox100이므로 3번째 데이터가 저장되어 있는 주소는 ox100 + 2 * 4 = ox108 이 된다.

따라서 배열은 메모리상에서 요소들이 연속적으로 존재하기때문에 간단한 계산으로 원하는 요소의 주소를 얻을 수 있지만, LinkedList는 요소들이 불연속적으로 위치하기때문에 처음부터 n 번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다. 그래서 LinkedLists는 데이터의 개수가 길어질수록 데이터를 읽어 오는 시간. 즉 access time이 길어진다는 단점이 있다.

 

- 컬렉션 읽기(접근시간) 추가/삭제 비교

ArrayList	빠르다	느리다	순차적인 추가,삭제는 더 빠름.
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐.

즉! 데이터의 개수가 변하지 않는 경우라면 ArrayList가 최상의 선택이 되겠고, 데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 더 나은 선택이다.


출처 : 자바의 정석