자바 중급 2편 - LinkedList

✅ ArrayList의 단점

• ArrayList는 내부에 배열을 사용해서 데이터를 보관하고 관리한다. 이로 인해 배열의 크기를 미리 확보해야하고, 
  데이터가 얼마나 추가될지 예측할 수 없는 경우 나머지 공간은 사용되지 않고 낭비되는 단점을 가진다.
• 배열의 중간에 데이터 추가
  • 배열의 앞이나 중간에 데이터를 추가하거나 삭제하는 경우 많은 데이터를 이동해야 하기 때문에 성능이 좋지 않다.

 

✅ List 자료구조

• 순서가 있고, 중복을 허용하는 자료구조를 리스트(List)라 한다.
• 노드와 연결
  • 낭비되는 메모리 없이 딱 필요한 만큼만 메모리를 확보해서 사용하고, 또 앞이나 중간에 데이터를 추가하거나 삭제할 때도 효율적인 자료구조 -> LinkedList
  • 단방향 LinkedList의 경우 데이터를 추가할 때 아래 코드와 같이 데이터를 저장하고, 그전 노드의 next의 추가한 데이터의 참조값을 넣어주어 노드를 연결시키면된다.

package com.example.collection.link;

public class Node {

    Object item;
    Node next;

    public Node(Object item) {
        this.item = item;
    }
//
//    @Override
//    public String toString() {
//        return "Node{" +
//                "item=" + item +
//                ", next=" + next +
//                '}';
//    }


    // {A -> B -> C}
    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();

        Node 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();

    }
}

 

Node first = new Node("A");
first.next = new Node("B");
first.next.next = new Node("C");

 

✅ Node 연결을 활용한 기능 구현

• 기능
  • 전체 탐색
  • 마지막 노드 찾기
  • 특정 index 노드 조회
  • 마지막에 데이터 추가

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

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

private static void add(Node node, Object param) {
    Node last = getLastNode(node);
    last.next = new Node(param);
}

 

✅ 직접 구현한 LinkedList(제네릭)

package com.example.collection.list;

public class MyLinkedList<E> implements MyList<E> {

    private Node<E> first;
    private int size;


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

    // 추가 코드
    @Override
    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++;


    }
    @Override
    public E set(int index, E e) {

        Node<E> x = getNode(index);

        E oldValue = x.item;
        x.item = e;

        return oldValue;

    }


    // 추가 코드
    @Override
    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;

    }

    private Node<E> getNode(int index) {

        Node<E> x = first;

        for (int i = 0; i < index; i++) {
            x = x.next;
        }

        return x;
    }
    @Override
    public E get(int index) {
        Node<E> node = getNode(index);
        return node.item;
    }
    @Override
    public int indexOf(E e) {

        int index = 0;
        for (Node<E> x = first; x != null; x = x.next) {

            if (x.item.equals(e)) {
                return index;
            }

            index++;

        }

        return -1;
    }
    @Override
    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() {
//        return "Node{" +
//                "item=" + item +
//                ", next=" + next +
//                '}';
//    }


        // {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();

        }
    }
}

 

배열 리스트 vs 연결 리스트 비교

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

 

• 조회가 빈번하고 뒤에 추가하는 경우 → 배열 리스트 추천
• 앞에 추가/삭제가 많은 경우 → 연결 리스트 추천