자바 연결 리스트 (Linked List feat.Node)

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

 

이번 시간에는 연결 리스트에 대해 알아보자.

 

이전 시간에는 배열 리스트를 배웠다.

 

그렇다면 연결 리스트는 무엇일까?

 

Node Class 만들며, 다음 Node의 참조값, item을 저장하는 객체이다.

 

Node에 다음 Node의 참조값을 저장해 나감으로써 연결된(Linked) 자료 구조임을 뜻한다.

 

모두 구현한 코드를 먼저 보자.

 

Node

public class Node {

    Object item;
    Node next;

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

    @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();
    }
}

 

MyLinkedListV3

package middle2.collection.linked;

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

    }
}

 

MyLinkedListV3 Main

public class MyLinkedListV3Main {
    public static void main(String[] args) {
        MyLinkedListV3<String> s = new MyLinkedListV3<>();
        s.add("a");
        s.add("b");
        s.add("c");
        String str = s.get(0);
        System.out.println("str = " + str);

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

 

Node 객체의 기능을 MyLinkedListV3에서 구현하고, MyLinkedListV3 Main에서 이 기능을 호출하여 사용하는 코드이다.

 

일단 제네릭을 구현함으로, 타입 안정성을 추가하였다.

 

연결 리스트에서는 아래와 같은 기능들이 필요하다.

 

add(data) // 데이터 추가

add(index, data) // index위치에 데이터 추가

getLastNode() // 리스트 마지막 데이터 참조값 반환

set(index, data) // index위치 데이터 수정

remove(index) // index위치 데이터 삭제

get(index) // index위치 데이터 반환

getNode(index) // index위치 데이터 참조값 반환

indexOf(data) // data 검색, 있으면 해당 index,  없으면 -1 반환

size() // 현재 리스트 길이 반환

 

그렇다면 배열리스트와 연결리스트의 차이점은 무엇일까?

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

 

※ 이는 단일 연결리스트에서의 시간 복잡도를 표현한다. 자바 Collection 프레임 워크에서 제공하는 연결 리스트는 양방향 연결 리스트 이므로 위 표와 시간 복잡도가 다르다. ( 현재는 Node에 다음 Node 참조값만 저장함 -> 단일)

 

배열 리스트의 경우, 앞에 추가(삭제)할 때, 나머지 데이터를 뒤로 한 칸씩 밀어줘야 하기에(당기거나) 시간복잡도가 O(n)이며, 맨 뒤는 역이다.

 

정리하면 조회할 일이 많이 없고 데이터가 뒤에 추가되면 연결리스트가 유리하고 나머지는 배열 리스트가 유리하다.