[Java 복습] 직접 구현해보는 LinkedList

목차

• 연결 리스트 구현해보기
• 특정 위치 추가, 삭제 메서드 추가
• 배열 리스트 VS 연결 리스트
• 제네릭 도입

 

연결 리스트 구현해보기

public class Node {

    Object item;
    Node next;

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

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

    private 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 x = getNode(index);
        return x.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 item) {
        Node x = first;
        for (int i = 0; i < size; i++) {
            if (item.equals(x.item)) {
                return i;
            } else {
                x = x.next;
            }
        }
        return -1;
    }

    public int size() {
        return size;
    }

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

 

 

주요 메서드

• void add(Object e)
  
  • 마지막에 데이터를 추가한다.
  • 새로운 노드를 만들고, 마지막 노드를 찾아서 새로운 노드를 마지막에 연결한다.
  • 만약 노드가 하나도 없다면 새로운 노드를 만들고 first 에 연결한다.
• Object set(int index, Object element)
  
  • 특정 위치에 있는 데이터를 찾아서 변경한다. 그리고 기존 값을 반환한다.
  • getNode(index)를 통해 특정 위치에 있는 노드를 찾고, 단순히 그 노드에 있는 item 데이터를 변경한다.
• Object get(int index)
  
  • 특정 위치에 있는 데이터를 반환한다.
  • getNode(index) 를 통해 특정 위치에 있는 노드를 찾고, 해당 노드에 있는 값을 반환한다.
• int indexOf(Object o)
  
  • 데이터를 검색하고, 검색된 위치를 반환한다.
  • 모든 노드를 순회하면서 equals() 를 사용해서 같은 데이터가 있는지 찾는다

 

구현된 연결 리스트 사용해보기

public class MyArrayListV1Main {

    public static void main(String[] args) {

        MyArrayListV1 list = new MyArrayListV1();
        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("listV1.size() = " + list.size());
        System.out.println("listV1.get(1) = " + list.get(1));
        System.out.println("listV1.indexOf('c') = " + list.indexOf("c"));
        System.out.println("listV1.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);
    }
}

== 데이터 추가==
MyLinkedListV1{first=null, size=0}
MyLinkedListV1{first=[a], size=1}
MyLinkedListV1{first=[a->b], size=2}
MyLinkedListV1{first=[a->b->c], size=3}
==기능 사용==
listV1.size() = 3
listV1.get(1) = b
listV1.indexOf('c') = 2
listV1.set(2, 'z') = c
MyLinkedListV1{first=[a->b->z], size=3}
==범위 초과==
MyLinkedListV1{first=[a->b->z->d], size=4}
MyLinkedListV1{first=[a->b->z->d->e], size=5}
MyLinkedListV1{first=[a->b->z->d->e->f], size=6}

• MyArrayListV1Main 에 있는 코드를 거의 그대로 사용했다.
• 참고로 기존에 만든 MyArrayListV1 리스트와 제공하는 기능이 같기 때문에 메서드 이름도 같게 맞추어두었다.
• 연결 리스트는 데이터를 추가할 때 마다 동적으로 노드가 늘어나기 때문에 범위를 초과하는 문제는 발생하지 않는다.

 

정리

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

배열 리스트는 중간에 데이터를 추가하거나 삭제할 때 기존 데이터를 한 칸씩 이동해야 하는 문제가 있었다.
연결 리스트는 이 문제를 어떻게 해결하는지 알아보자.

 

 

특정 위치 추가, 삭제 기능 메서드 추가

public class MyLinkedListV2 {

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

    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 remove(int index) {
        Node removeNode = getNode(index);
        Object removeItem = removeNode.item;
        if (index == 0) {
            first = removeNode.next;
        } else {
            Node prev = getNode(index - 1);
            prev.next = removeNode.next;
        }
        removeNode.next = null;
        removeNode.item = null;
        size--;
        return removeItem;
    }

    public Object get(int index) {
        Node x = getNode(index);
        return x.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 "MyLinkedListV2{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }
}

public class MyLinkedListV2Main {

    public static void main(String[] args) {

        MyLinkedListV2 list = new MyLinkedListV2();
        // 마지막에 추가 // O(n) => getLastNode();
        list.add("a");
        list.add("b");
        list.add("c");
        System.out.println(list);
        
        // 첫 번째 항목에 추가, 삭제
        System.out.println("첫 번째 항목 추가");
        list.add(0, "d"); // O(1)
        System.out.println(list);

        System.out.println("첫 번째 항목 삭제");
        list.remove(0); // remove First O(1)
        System.out.println(list);
        
        // 중간 항목에 추가, 삭제
        System.out.println("중간 항목에 추가");
        list.add(1, "e"); // O(n)
        System.out.println(list);

        System.out.println("중간 항목에 삭제");
        list.remove(1); // remove O(n)
        System.out.println(list);
    }
}

MyLinkedListV2{first=[a->b->c], size=3}

첫 번째 항목 추가
MyLinkedListV2{first=[d->a->b->c], size=4}

첫 번째 항목 삭제
MyLinkedListV2{first=[a->b->c], size=3}

중간 항목에 추가
MyLinkedListV2{first=[a->e->b->c], size=4}

중간 항목에 삭제
MyLinkedListV2{first=[a->b->c], size=3}

 

 

 

 

 

 

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

데이터를 조회할 일이 많고, 뒷 부분에 데이터를 추가한다면 배열 리스트가 보통 더 좋은 성능을 제공한다. 

앞쪽의 데이터를 추가하거나 삭제할 일이 많다면 연결 리스트를 사용하는 것이 보통 더 좋은 성능을 제공한다.

 

 

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

우리가 구현한 연결 리스트는 한 방향으로만 이동하는 단일 연결 리스트다. 

노드를 앞뒤로 모두 연결하는 이중 연결 리스트를 사용하면 성능을 더 개선할 수 있다.

 

자바가 제공하는 연결 리스트는 이중 연결 리스트다. 

추가로 자바가 제공하는 연결 리스트는 마지막 노드를 참조하는 변수를 가지고 있어서,

뒤에 추가하거나 삭제하는 삭제하는 경우에도 O(1)의 성능을 제공한다.

 

 

이중 연결 리스트 예시

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

 

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

public class LinkedList {
    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++;
    }

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

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

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

    public E get(int index) {
        Node<E> x = getNode(index);
        return x.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 "MyLinkedListV2{" +
                "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;
            sb.append("[");

            while (x != null) {
                sb.append(x.item);
                if (x.next != null) {
                    sb.append("->");
                }
                x = x.next;
            }

            sb.append("]");
            return sb.toString();
        }
    }
}

public class MyLinkedListV3Main {

    public static void main(String[] args) {

        MyLinkedListV3<String> stringList = new MyLinkedListV3<>();
        stringList.add("a");
        stringList.add("b");
        stringList.add("c");
        String string = stringList.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(2);
        System.out.println("integer = " + integer);
    }
}

string = a
integer = 3