컬렉션 프레임워크 - LinkedList

 

노드와 연결 (1)

이전에 배웠던 ArrayList는 내부에 배열을 사용해 데이터를 보관하고 관리한다. 이로인해 발생하는 단점은

배열을 미리 확보해야하기 때문에 사용하지 않는 공간을 낭비하게 된다.

중간에 데이터를 추가한다면 공간을 확보하기 위해 데이터를 한칸씩 이동해야하는 문제가 발생하며

이 방법은 성능이 좋지 않은 방법이다.

 

낭비되지 않는 메모리 없이 필요한만큼 메모리를 확보해서 사용하고, 데이터를 추가하거나 삭제할 때

효율적으로 사용할 수 있는 자료구조가 있는데, 노드를 만들고 각 노드를 서로 연결하는 방식이다.

 

public class Node {

    Object item;
    Node next;

    public Node(Object item) {
        this.item = item;
    }
}

 

노드 클래스는 내부에 저장할 데이터 item, 다음 연결할 노드의 참조인 next를 가진다.

이 노드 클래스를 사용해서 데이터 A, B, C를 순서대로 연결해보자

 

public class NodeMain1 {

    public static void main(String[] args) {
        // 노드 생성하고 연결하기 A -> B -> C
        Node first = new Node("A");
        first.next = new Node("B");
        first.next.next = new Node("C");
}

 

 

first에 첫번째 노드를 생성했다. 그 뒤에 next로 다음 Node 인스턴스를 생성하고 "B"를 넣어준다.

-- 그 뒤는 반복 --

 

연결된 노드를 찾는법

System.out.println("first.item = " + first.item);
System.out.println("first.next.item = " + first.next.item);
System.out.println("first.next.next.item = " + first.next.next.item);

 

Node first를 통해 첫번째 노드를 찾을 수 있다. 첫번째 노드의 node.next를 호출하면 두번째 노드를 구할 수 있고,

두번째 노드의 node.next를 호출하면 세번째 노드를 찾을 수 있다.

첫번째 노드의 node.next.next를 호출하면 세번째 노드를 구할 수 있다.

 

 

모든 노드 탐색하기

 

Node x = first;
while (x != null) {
    System.out.println(x.item);
    x = x.next ;
}

 

x는 처음 노드부터 순서대로 이동하며 모든 노드를 가리킨다.

처음엔 x01을 참조 후 while문을 통해 다음 노드를 참조하게 된다.

노드의 값이 (x)가 null일 경우 while문은 종료되는 코드이다.

 

toString을 통해 노드 연결구조 확인하기

[A->B->C]와 같이 출력되게 코드를 구현해보자

IDE에서 기본 제공하는 toString으로 출력을 하게되면

Node{item=A, next=Node{item=B, next=Node{item=C, next=null}}}

 

이런 형식의 결과가 출력된다. 노드의 노드의 노드를 출력하기 때문에 한눈에 보기 힘들다.

@Override
public String toString() {
    StringBuilder sb = new StringBuilder();
    Node x = this; // x01
    sb.append("[");
    while (x != null) {
        sb.append(x.item);
        if (x.next != null) {
            sb.append("->");
        }
        x = x.next;
    }
    sb.append("]");
    return sb.toString();
}

 

반복문에서 문자를 더하기 때문에 StringBuilder를 사용하는게 효과적이다.

이렇게 toString을 작성하면 A->B->C 형태의 결과가 출력된다.

 

노드 연결 - 메서드 추가

 

모든 노드 탐색, 마지막 노드 조회, 특정 index 노드 조회, 노드에 데이터 추가 기능을 만들어 볼 것이다.

 

// 모든 노드 탐색
private static void printAll(Node node) {
    Node x = node;
    while (x != null) {
        System.out.println(x.item);
        x = x.next;
    }
}

 

이전에 했던 것 처럼 x.next가 null일때까지 반목문을 통해 모든 노드를 탐색할 수 있다.

 

// 마지막 노드 탐색
private static Node getLastNode(Node node) {
    Node x = node;
    while (x.next != null) {
        System.out.println(x.item);
        x = x.next;
    }
    return x;
}

 

위 코드와 매우 유사하지만, x.next가 null일때까지 반목문을 통해 마지막 노드를 탐색할 수 있다.

(x.next가 null이면 그 뒤엔 노드가 없다는 뜻)

 

// 특정 index 노드 조회
private static Node getNode(Node node, int index) {
    Node x = node;
    for (int i = 0; i < index; i++) {
        x = x.next;
    }
    return x;
}

 

특정 인덱스까지 for문을 돌린 후 x.next의 값을 출력한다. (x.next == 특정index의 node 값)

 

// 데이터 추가
private static void add(Node node, String param) {
    Node latsNode = getLastNode(node);
    latsNode.next = new Node(param);
}

 

마지막 노드를 탐색한 후, next에 새로운 노드 인스턴스를 생성하면 된다.

 

LinkedArray 구현

 

이번엔 배열이 아닌 노드와 연결구조를 통해서 LinkedList를 만들어보자.

LinkedList는 ArrayList의 단점인 메모리 낭비, 중간 위치의 데이터 추가/삭제에 대한 성능문제를 어느정도 극복할 수 있다.

- 순서가 있고, 중복을 허용하는 자료 구조를 List라고 한다.

 

이전에 공부한 ArrayList도 결국 같은 List이다. 내부에서 배열을 사용하냐 노드 연결구조를 사용하냐 차이이다.

Array건 Linked건 리스트 자료 구조이기 때문에 리스트를 사용하는 개발자 입장에선 비슷하게 느껴져야 한다.

쉽게 말해 뭘 쓰건 내부가 어떻게 돌아가는지 몰라도 순서가 있고 중복을 허용하는구나 하고 사용할 수 있어야한다.

 

package collection.link;

public class MyLinkedListV1 {

    private Node first;
    private int size = 0;

    public void add(Object e) {
        Node newNode = new Node(e);
        if (first == null) {
            first = newNode;
        } else {
            Node lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++;
    }

    private Node getLastNode() {
        Node x = first;
        while (x.next != null) {
            x = x.next;
        }
        return x;
    }

    public Object set(int index, Object element) {
        Node x = getNode(index);
        Object oldValue = x.item;
        x.item = element;
        return oldValue;
    }

    public Object get(int index) {
        Node node = getNode(index);
        return node.item;
    }

    private Node getNode(int index) {
        Node x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;

    }

    public int indexOf(Object o) {
        int index = 0;
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "MyLinkedListV1{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }
}

 

메서드 설명

 

void add(Object e)

- 마지막에 데이터를 추가한다.

- 새로운 노드를 생성하고, 마지막 노드를 찾아서 연결한다.

- 만약 노드가 없다면 (첫번째가 null) 노드를 생성하고 first에 연결한다.

 

Object set(int index, Object element)

- 특정 위치에 있는 데이터를 찾아서 변경하고 기존값을 리턴한다.

- getNode 메서드로 특정 인덱스에 있는 노드를 찾고, x.item에 새로운 element를 입력한다.

 

Object get(int index)

- 특정 위치의 데이터를 반환한다.

- getNode 메서드로 특정 위치의 데이터를 찾고 반환한다.

 

int indexOf(Object o)

- 데이터를 검색하고 검색된 위치(인덱스)를 반환한다.

- 모든 노드를 순회하며 equals를 사용해 검색한다.

 

package collection.link;

public class MyLinkedListV1Main {

    public static void main(String[] args) {
        MyLinkedListV1 list = new MyLinkedListV1();
        System.out.println("== 데이터 추가 ==");
        System.out.println(list);
        list.add("a");
        System.out.println(list);
        list.add("b");
        System.out.println(list);
        list.add("c");
        System.out.println(list);

        System.out.println("== 기능 사용 ==");
        System.out.println("list.size() = " + list.size());
        System.out.println("list.get() = " + list.get(1));
        System.out.println("list.indexOf(\"c\") = " + list.indexOf("c"));
        System.out.println("list.set(2, \"z\") = " + list.set(2, "z"));
        System.out.println(list);

        System.out.println("== 범위 초과 ==");
        list.add("d");
        System.out.println(list);
        list.add("e");
        System.out.println(list);

         // 범위 초과, capacity 가 늘어나지 않으면 예외 발생
         list.add("f");
         System.out.println(list);
    }
}

 

이전에 사용했던 ArrayList의 Main코드를 그대로 가져왔으나 잘 작동하는것을 확인할 수 있다.

연결 리스트는 데이터를 추가할 때 마다 노드가 늘어나기 때문에 범위 초과에 대한 에러가 발생하지 않는다.

 

연결 리스트와 빅오

 

get(int index) : O(n)

- 배열은 인덱스로 데이터를 즉시 찾을 수 있기에 O(1)이지만, 연결 리스트는 배열이 아니다.

단지 다음 노드의 참조가 있을 뿐이기에 다음 노드를 계속해서 반복해서 찾아야한다. 따라서 O(n) / 성능 나쁨

 

void add(Object e) : O(n)

- 마지막에 데이터를 추가한다. 마지막 노드를 찾는데 노드를 처음부터 반복해서 찾아가야한다.  성능 나쁨

 

Object set(int index, Object element) : O(n)

- 특정 위치를 찾아서 변경한다. 특정 위치를 찾아가는데 반복이 발생한다. 성능 나쁨

 

int indexOf(Object o) : O(n)

- 데이터를 검색하고, 검색된 위치를 반환한다.

- 모든 노드를 순회하면서 equals()로 같은 값이 있는지 하나씩 찾아봐야 한다. 성능 나쁨

 

배열과 달리 모든 메서드가 O(n)으로 좋지 않는 성능을 나타낸다. 그럼 연결 리스트는 왜 쓰는 것일까?

 

LinkedList - 추가와 삭제

 

추가와 삭제하는 메서드를 구현할건데, 어떤식으로 구현해야 하는지 그림과 코드를 보자

 

추가

첫 번째 노드에 데이터 추가 d -> a -> b -> c

 

중간에 데이터 추가 a -> e -> b -> c

public void add(int index, Object e) {
    Node newNode = new Node(e);
    if (index == 0) {
        newNode.next = first;
        first = newNode;
    } else {
        Node prev = getNode(index - 1);
        newNode.next = prev.next;
        prev.next = newNode;
    }
    size++;
}

 

따로 설명할 필요는 없을 것 같다. (이해함)

나중에 까먹으면 그림과 코드를 보면서 천천히 이해해보자

 

삭제

 

첫번째 노드 삭제 / 이후 GC 과정

중간 노드 삭제 / 이후 GC 과정

public Object remove(int index) {
    Node removeNode = getNode(index);
    Object removedItem = removeNode.item;
    if (index == 0) {
        first = removeNode.next;
    } else {
        Node prev = getNode(index - 1);
        prev.next = removeNode.next;
    }
    removeNode.item = null;
    removeNode.next = null;
    size--;
    return removedItem;
}

 

 

어찌됐건 결론은 노드끼리 연결을 다시 잘 해주면 된다는 것이다.

그 과정을 김영한님 강의에선 친절히 그림으로 설명해주고 있다.

 

ArrayList와 LinkedList의 성능을 잘 비교해 리스트를 사용하는 것이 중요하다.

참고로 우리가 구현한 LinkedList는 단방향이다. 양방향 연결 리스트도 있다 (나중에 학습할 것임) 

 

제네릭 도입

package collection.link;

public class MyLinkedListV3<E> {

    private Node first;
    private int size = 0;

    public void add(E e) {
        Node<E> newNode = new Node<>(e);
        if (first == null) {
            first = newNode;
        } else {
            Node<E> lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++;
    }

    private Node<E> getLastNode() {
        Node<E> x = first;
        while (x.next != null) {
            x = x.next;
        }
        return x;
    }

    // 추가 코드
    public void add(int index, E e) {
        Node<E> newNode = new Node<>(e);
        if (index == 0) {
            newNode.next = first;
            first = newNode;
        } else {
            Node<E> prev = getNode(index - 1);
            newNode.next = prev.next;
            prev.next = newNode;
        }
        size++;
    }

    public Object set(int index, E element) {
        Node<E> x = getNode(index);
        E oldValue = x.item;
        x.item = element;
        return oldValue;
    }

    // 추가 코드
    public E remove(int index) {
        Node<E> removeNode = getNode(index);
        E removedItem = removeNode.item;
        if (index == 0) {
            first = removeNode.next;
        } else {
            Node<E> prev = getNode(index - 1);
            prev.next = removeNode.next;
        }
        removeNode.item = null;
        removeNode.next = null;
        size--;
        return removedItem;
    }

    public E get(int index) {
        Node<E> node = getNode(index);
        return node.item;
    }

    private Node<E> getNode(int index) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;

    }

    public int indexOf(E o) {
        int index = 0;
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "MyLinkedListV1{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }

    private static class Node<E> {
        E item;
        Node<E> next;

        public Node(E item) {
            this.item = item;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            Node<E> x = this; // x01
            sb.append("[");
            while (x != null) {
                sb.append(x.item);
                if (x.next != null) {
                    sb.append("->");
                }
                x = x.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }
}

 

사실 Node<> 클래스는 MyLinkedList에서만 사용한다. 따라서 중첩클래스로 구현을 해줬다.

코드 변경사항은 리턴타입 / 매개변수를 Object -> E로 바꾼것 밖에 없다.

이로써 원하는 타입만을 입력할 수 있게 변경했다.

 

 

이번 섹션은 ArrayList와 LinkedList의 차이를 중점으로 학습하면 될 것 같다.

어떤부분에서 O(1)인지 O(n)인지 알고 있으면 될 것 같다.