컬렉션 프레임워크 - LinkedList

노드와 연결

낭비되는 메모리 없이 딱 필요한 만큼만 메모리르 ㄹ확보해서 사용하고, 또 앞이나 중간에 데이터를 추가하거나 삭제할 때도 효율적인 자료 구조가 있는데, 바로 노드를 만들고 각 노드를 서로 연결하는 방식이다.

 

public class Node {
	Object item;
    Node next;
}

---------------------------------------------------

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");

        System.out.println("모든 노드 탐색하기");
        Node x = first;
        while (x != null) {
            System.out.println(x.item);
            x = x.next;
        }
    }
}

 

---

직접 구현하는 연결 리스트

시작

 

연결 리스트는 배열 리스트의 단점인, 메모리 낭비, 중간 위치의 데이터 추가에 대한 성능문제를 어느정도 극복할 수 있다.

 

리스트 자료 구조

순서가 있고, 중복을 허용하는 자료 구조를 리스트(List)라고 한다.

 

연결 리스트와 빅오

Object get(int index)

• 특정 위치에 있는 데이터를 반환한다
• O(n)
  • 배열은 인덱스로 원하는 데이터를 즉시 찾을 수 있다. 따라서 배열을 사용하는 배열 리스트(ArrayList)도 인덱스로 조회시 O(1)의 빠른 성능을 보장한다. 하지만 연결 ㅣㄹ슽으에서 사용하는 노드들은 배열이 아니다. 단지 다음 노드에 대한 참조가 있을 뿐이다. 따라서 인덱스로 원하는 위치의 데이터를 찾으려며 ㄴ인덱스 숫자 만큼 다음 노드를 반복해서 찾아야 한다. 따라서 인덱스 조회 성능이 나쁘다.
  • 특정 위치의 노드를 찾는데 O(n)이 걸린다.

void add(Obejct e)

• 마지막에 데이터를 추가한다.
• O(n)
  • 마지막 노드를 찾는데 O(n)이 소요된다. 마지막 노드에 새로운 노드를 추가하는데 O(1)이 걸린다. 따라서 O(n)이다.

Object set(int index, Object)

• 특정 위치에 있는 데이터를 찾아서 변경한다. 그리고 기존 값을 반환한다.
• O(n)
  • 특정 위치의 노드를 찾는데 O(n)이 걸린다.

int indexOf(Obejct o)

• 데이터를 검색하고, 검색된 위치를 반환한다.
• O(n)
  • 모든 노드를 순회하면서 equals()를 사용해서 같은 데이터 코드가 있는지 찾는다.

 

정리

• 련결 리스트를 통해 데이터를 추가하는 방식은 꼭 필요한 메모리만 사용한다. 따라서 배열 연결 리스트의 단점인 메모리 낭비를 해결할 수 있었다. 
  • 물론 연결을 유지하기 위한 추가 메모리가 사용되는 단점도 함께 존재한다.

---

 

추가와 삭제1

연결 리스트와 배열 리스트 둘다 중간에 있는 항목을 추가하거나 삭제하는 경우 둘다 같은 O(n)이다.

 

---

 

추가와 삭제2

직접 만든 배열 리스트와 연결 리스트의 성능 비교 표

기능	배열 리스트	연결 리스트
인덱스 조회	O(1)	O(n)
검색	O(n)	O(n)
앞에 추가(삭제)	O(n)	O(1)
뒤에 추가(삭제)	O(1)	O(n)
평균 추가(삭제)	O(n)	O(n)

 

배열 리스트 vs 연결 리스트 사용

데이터를 조회할 일이 많고, 뒷 부분에 데이터를 추가한다면 배열 리스트가 보통 더 좋은 성능을 제공한다. 앞쪽의 데이터를 추가하거나 삭제할 일이 많다면 연결 리스트를 사용하는 것이 보통 더 좋은 성능을 제공한다.

 

참고 - 단일 연결 리스트, 이중 연결 리스트

우리가 구현한 연결 리스트는 한 방향으로만 이동하는 단일 연결 리스트다. 노드를 앞뒤로 모두 연결하는 이중 연결 리스트를 사용하면 성능을 더 개선할 수 있다.

자바가 제공하는 견결 이스트는 이중 리스트다. 추가로 자바가 제공하는 연결 리스트는 마지막 노드를 참조하는 변수를 가지고 있어서, 뒤에 추가하거나 삭제하는 경우에도 O(1) 성능을 제공한다.

 

이중 연결 리스트 예시

public class Node {
    Object item;
    Node next; //다음 노드 참조
    Node prev; //이전 노드 참조
}

 

마지막 노드를 참조하는 연결 리스트

public class Node {
    private Node first;
    private Node last; //마지막 노드 참조
    private int size =0;
}

---

제네릭 도입

package collection.link;

public class MyLinkedListV3 <E> {

    private Node<E> 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++;
    }

    //추가  코드
    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 e) {
        Node<E> x = getNode(index);
        E oldValue = x.item;
        x.item = e;
        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> prevNode = getNode(index - 1);
            prevNode.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;
    }

    public 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 e) {
        int index = 0;
        for (Node<E> x = first; x != null; x = x.next) {
            if (e.equals(x.item)) {
                return index;
            }
            index++;
        }
        return -1;
    }

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

    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;
        }

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

 

중첩 클래스는 특정 클래스 안에서만 사용될 때 주로 사용한다.

이럴 때 중첩 클래스를 사용하면 특정 클래스 안으로 클래스 선언을 숨길 수 있다.

중첩 클래스를 사용하면 MyLinkedListV3 입장에서 외부에 있는 Node 클래스보다 내부에 선언한 Node 클래스를 먼저 사용한다.

 

package collection.link;

public class MyLinkedListV3Main {

    public static void main(String[] args) {
        MyLinkedListV3<String> list = new MyLinkedListV3<>();
        //마지막에 추가 //O(n)
        list.add("a");
        list.add("b");
        list.add("c");
        String string = list.get(0);
        System.out.println("string = " + string);

        MyLinkedListV3<Integer> intList = new MyLinkedListV3<>();
        intList.add(1);
        intList.add(2);
        intList.add(3);
        Integer integer = intList.get(0);
        System.out.println("integer = " +integer);
    }
}

 

실행 결과

string = a
integer = 1

 

 

 

 

 

 

출처 - 김영한의 실전 자바 중급 1편