자료구조 리스트(List)

연결 리스트(Linked List)

크기를 미리 정하는 배열과 달리 데이터가 들어올 때 마다 동적으로 메모리를 할당하는 자료구조
Node라는 저장공간으로 데이터와, 다음 노드로 갈 수 있는 링크를 포함하고있다.

리스트의 종류

1. 단일 연결 리스트
2. 이중 연결 리스트
3. 원형 연결 리스트
   
   

코틀린에서 연결리스트 구현

val linkedList : LinkedList<Int> = LinkedList(listOf(1,2,3))

private static class Node<E> {
        E item; // 데이터
        Node<E> next; // 다음노드
        Node<E> prev; // 이전노드

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

자바에 구현되어있는 LinkedList를 사용한다.
마지막 노드에 데이터가 없는경우에는 null로 처리한다.

단일 연결 리스트

다음 노드를 알려주는 링크가 하나인 리스트(한 방향으로만 이동 가능)

이중 연결 리스트

다음과 이전 노드를 알려주는 링크가 있는 리스트(양방향으로 이동 가능)

원형 연결 리스트

단일 연결 리스트일수도, 이중 연결 리스트일수도 있다.
마지막 노드의 링크가 첫번째 노드를 가르킨다

노드의 삽입(추가)

1. 첫 노드에 추가

addFirst 함수 사용

val linkedList : LinkedList<Int> = LinkedList(listOf(1,2,3))
linkedList.addFirst(3)

addFirst() 메서드에 들어가보면

public void addFirst(E e) {
    linkFirst(e);
}

호출시 linkFirst() 메서드를 호출하는게 보인다.

다시 linkFirst() 메서드에 들어가보면

private void linkFirst(E e) {
    final Node<E> f = first; // 첫 번째 노드 (1)
    final Node<E> newNode = new Node<>(null, e, f); // 새로운 노드 (2)
    first = newNode; (3)
    if (f == null) (4)
        last = newNode; (5)
    else
        f.prev = newNode; (6)
    size++; (7)
    modCount++; (8)
}

1, 2 : 새로운 노드가 추가될 때, 첫 번째 노드에 새로운 노드를 삽입.
3 : 첫 번째 노드를 새롭게 추가된 노드로 변경
4 : 빈 리스트에 addFirst() 메서드를 호출 한 경우(첫 번째 노드가 없는경우)
5 : 마지막 노드에 추가한 노드 삽입
6 : 빈 리스트가 아니라면 첫 번째 노드(여기선 newNode가 추가되기전 노드)에 이전 링크를 추가 된 노드로
7, 8 : 리스트의 사이즈 증가, 수정된 횟수 증가

출력 결과 : 4, 1, 2, 3

2. 마지막 노드에 추가

val linkedList : LinkedList<Int> = LinkedList(listOf(1,2,3))
linkedList.addLast(3)

addLast() 메서드 사용 첫 번째 노드에 추가와같이 디테일하게 들어가보면

public void addLast(E e) {
    linkLast(e);
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

linkLast() 메서드가 있다.
코드를 분석해보면 위 addFirst()메서드와 비슷하다

3. 특정 위치에 추가

val linkedList : LinkedList<Int> = LinkedList(listOf(1,2,3))
linkedList.add(2, 5)

특정 위치에 추가도 첫 노드에 추가함수와 같지만, 인자가 다르다

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

특정 위치에 삽입하고 싶은 인덱스로 연산을 실행한다.
해당 인덱스가 리스트의 사이즈만큼 shift연산(코틀린에서는 shr, shl로 표기)

코드 분석해보니 해당 인덱스의 노드를 반환해준다.

입력한 인덱스가(위치) 현재 리스트의 사이즈와 같다면, listLast()호출
같지 않다면, linkBefore()호출

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode; // 연결
    if (pred == null)
        first = newNode; // 연결 (사이즈가 없는경우)
    else
        pred.next = newNode; // 연결
    size++;
    modCount++;
}

반환해준 노드와 삽입하고 싶은 원소를 로직대로 실행해보면

새로운 노드를 이전노드와 다음노드로 연결시켜준다.

노드의 삭제

삭제는 removeFirst(), removeLast(), removeAt() 으로 노드를 삭제할 수 있다.
메서드 이름에서 유추가 가능하듯이 해당 기능은 설명하지않겠다.

해당 메서드를 호출하면 공통적으로 실행되는 메서드는 바로 unLink이다

unlinkFirst(), unLinkLast(), unLink() 셋 메서드 다 위에 노드의 삽입 메서드와 비슷하니 unLinkFirst()만 분석해보자면

private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item; // 첫 노드의 원소
        final Node<E> next = f.next; // 첫 노드의 next link
        f.item = null; // 원소 삭제
        f.next = null; // help GC // next link 삭제
        first = next; // 첫 노드를 삭제되기전 노드의 다음 노드로 지정
        if (next == null) 
            last = null; // 빈 리스트라면 가르키는 노드 없음.
        else
            next.prev = null; // 첫 노드의 이전 노드를 없음 처리
        size--;
        modCount++;
        return element;
    }

코틀린의 LinkedList를 공부해보면서 들은 생각은 위 정리한 종류중에 이중 연결리스트 기반으로 구현되어있는거같다. 원형 연결리스트는 원형 큐로 구현할 수 있다고는 들었지만, 단일 연결 리스트는 새롭게 구현해야하나? 라는 생각이 들었다.

정리(시간복잡도)

탐색 : O(n) LinkedList.java를 들어가보면 get()이나 indexOf()의 함수는 해당 리스트의 size를 기반으로 for문을 실행한다.

추가/삭제(처음, 마지막 노드일 경우 ) : O(1)
특정 위치일 경우 : O(n)