[Java/김영한] LinkedList

https://inf.run/sDjcZ

김영한의 실전 자바 - 중급 2편| 김영한 - 인프런 강의

이 링크를 통해 구매하시면 제가 수익을 받을 수 있어요. 🤗

 

 

노드와 연결

배열 리스트의 단점

배열 리스트는 내부에 배열을 사용해서 데이터를 보관하고 관리한다. 이로 인해 다음과 같은 단점을 가진다.

• 사용하지 않는 공간 낭비

• 데이터 추가·삭제 시 많은 이동이 필요해 성능 저하됨

---

노드와 연결

노드와 연결

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

 

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

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

 

 

• `Node` 인스턴스를 생성하고, 각 `item`에 "A", "B", "C"를 넣어준다.
• 각 노드의 `next` 필드를 이용해 A → B → C 순서로 연결한다. (`A.next = B`, `B.next = C`)
  • 이렇게 하면 첫 번째 노드는 두 번째 노드와, 두 번째 노드는 세 번째 노드와 서로 연결된다.
• 첫 번째 노드의 `node.next`를 호출하면 두 번째 노드를 구할 수 있다.
• 두 번째 노드의 `node.next`를 호출하면 세 번째 노드를 구할 수 있다.
• 첫 번째 노드의 `node.next.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;
        }
    }
}

 

실행 결과

모든 노드 탐색하기
A
B 
C

 

 

다양한 기능

모든 노드 탐색하기

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

• 다음 노드가 없을 때까지 반복해서 노드의 데이터 출력

 

마지막 노드 조회하기

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

• 노드를 순서대로 탐색하면서 `Node.next`의 참조값이 `null`인 노드를 찾아서 반환한다.

 

특정 index의 노드 조회하기

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

• `index`의 수 만큼만 반복해서 이동하면 원하는 위치의 노드를 찾을 수 있다.

 

데이터 추가하기

void add(Node node, String param) {
    Node lastNode = getLastNode(node);
    lastNode.next = new Node(param);
}

• 새로운 노드를 만들고, 마지막 노드에 새로 만든 노드를 연결한다.

---

직접 구현하는 연결 리스트

노드와 연결 구조를 통해서 만든 리스트를 연결 리스트(`LinkedList`)라 한다. 

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

 

리스트 자료 구조

배열 리스트를 사용하든 연결 리스트를 사용하든 둘 다 리스트 자료 구조이기 때문에 리스트를 사용하는 개발자 입장에서는 거의 비슷하게 느껴져야 한다. 쉽게 이야기해서 리스트를 사용하는 개발자 입장에서 `MyArrayList`를 사용하든 `MyLinkedList`를 사용하든 내부가 어떻게 돌아가는지 몰라도 그냥 순서가 있고, 중복을 허용하는 자료 구조구나 생각하고 사용할 수 있어야 한다.

 

 

단순 구현

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

• `MyArrayListMain1`에 있는 코드를 거의 그대로 사용했다. 
• 연결 리스트는 데이터를 추가할 때마다 동적으로 노드가 늘어나기 때문에 범위를 초과하는 문제는 발생하지 않는다.

---

추가와 삭제

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

• 특정 위치에 데이터를 추가한다.
• 내부에서 노드도 함께 추가된다.

 

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

• 특정 위치에 있는 데이터를 제거한다.
• 내부에서 노드도 함께 제거된다.

---

정리

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

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

• 배열 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(1)으로 빠르게 찾지만, 추가나 삭제 이후에 데이터를 한 칸씩 밀어야 한다. 이 부분이 O(n)으로 오래 걸린다.
• 연결 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(n)으로 느리게 찾지만, 찾은 이후에는 일부 노드의 참조값만 변경하면 되므로 이 부분은 O(1)로 빠르다.

 

배열 리스트 vs 연결 리스트

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

---

제네릭 도입

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

    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 E 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> temp = this;
            sb.append("[");
            while (temp != null) {
                sb.append(temp.item);
                if (temp.next != null) {
                    sb.append("->");
                }
                temp = temp.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }
}

• `Object`로 처리하던 부분을 타입 매개변수 `<E>`로 변경했다.
• 정적 중첩 클래스로 새로 선언한 `Node<E>`도 제네릭 타입으로 선언했다.