LinkedList(연결리스트) with Java

LinkedList 는 Node 객체 여러개를 이용해서 Node 끼리 연결되어 있는 자료구조이다.

Node에는 Data와 다음 노드의 주소 Reference를 갖고 있기 때문에 배열과 다르게 연속적인 메모리에 할당되어 있지 않아도 된다. 

Java 에서는 List 인터페이스를 이용해 LinkedList를 구현하고 있다.

 

LinkedList는 단방향, 양방향, 원형 연결 등이 있지만 이번에는 Single LinkedList를 구현해보겠다(List 인터페이스를 구현하지 않고)

 

https://visualgo.net/en/list

Linked List (Single, Doubly), Stack, Queue, Deque - VisuAlgo

 

Node

LinkedList에서 중요한 Node 객체이다. Node는 담을 데이터와 다음 노드의 주소를 담고 있는 객체이다.

    private class Node<T> {
        private T data;
        private Node next;

        public Node(T value) {
            this.data = value;
            this.next = null;
        }

        @Override
        public String toString() {
            return String.valueOf(this.data);
        }
    }

이번 구현에서는 LinkedList 내부에 Node 클래스를 정의해서 사용한다.

• T data : 저장할 데이터
• Node next : 다음 Node의 주소

생성자를 통해서 Node를 생성하면 값은 할당해주고 다음 노드의 주소는 알지 못하기 때문에 null로 초기화한다.

 

MyLinkedList

 

public class MyLinkedList<T> {
    private Node<T> head;
    private Node<T> tail;
    private int size;
}

• Node<T> head : LinkedList의 제일 첫번째 요소
• Node<T> tail : LinkedList의 제일 마지막 요소
• int size : LinkedList의 크기

LinkedList의 삽입, 삭제, 읽기 등의 메소드를 구현해보겠다

 

[삽입] add(T value), add(int index, T value), addFirst(), addLast()

우선 LinkedList에서는 다음 노드에 대한 주소 정보가 중요하기 때문에 삽입, 삭제 등을 하기 위해서는 이전 노드의 정보가 필수다. 그렇기 때문에 먼저 연산을 수행하고자 하는 노드의 이전 노드를 찾는 메소드를 구현할 것이다.

 

    private Node<T> node(int index) {
        Node<T> x = head;
        for (int i=0; i<index; i++) {
            x = x.next;
        }
        return x;
    }

리스트에서 탐색을 하기 위해서는 제일 첫번째 노드의 주소를 알아야하기 때문에 x에 head의 주소를 넣어준다.

이후 매개변수로 넘어온 index의 전까지 루프를 돌면서 Node x 의 다음 노드를 탐색한다.

 

index로 3이 들어온다면 index 2번째인 노드를 반환할 것이다.

 

addFirst(T value)

 

    public void addFirst(T value) {
        Node<T> newNode = new Node<>(value);
        newNode.next = head;
        head = newNode;
        size++;

        if (head.next == null) {
            tail = head;
        }
    }

맨 앞에 노드를 추가하는 메소드다.

• newNode.next : 노드를 새로 생성할 때 넘어온 값으로 노드를 생성한다. 이 노드는 맨 앞에 위치해야하기 때문에 이 노드의 다음 노드는 head이다. 
• head = newNode : newNode.next는 head이지만 아직 head는 첫번째 노드인 newNode를 가르키고 있지 않기 때문에 head에 newNode를 할당해준다
• 새로운 노드를 추가했기 때문에 크기를 증가시킨다

첫번째 노드의 다음 노드가 null 이라는 것은 요소가 하나밖에 없다는 것이다. 즉 꼬리노드 역시 head라는 것이다.

 

addLast(T value)

    public void addLast(T value) {
        Node<T> newNode = new Node<T>(value);

        if (size == 0) {
            addFirst(value);
        }
        else {
            tail.next = newNode;
            tail = newNode;
            size++;
        }
    }

• size가 0이라는 것은 요소가 없다는 것이다. 즉 맨앞에 요소를 삽입하는 것과 같기 때문에 addFirst 메소드를 호출해주면 된다.
• 그렇지 않으면 현재 리스트의 마지막 요소를 가져와서, 그 요소가 참조하고 있는 다음 노드의 주소에 추가하고자 할 노드를 넣어주면 된다.
• addFirst()와 같이 넣어준 이후 tail은 새로 넣은 마지막 요소를 참조하게 해주면 된다

 

add(T value)

    public boolean add(T value) {
        addLast(value);
        return true;
    }

add를 한다는 것은 사실 마지막 노드 이후에 계속 추가하는 것과 같기 때문에 addLast 메소드를 호출하는 것과 같다

 

add(int index, T value)

   public void add(int index, T value) {
        if (index == 0) {
            addFirst(value);
        }
        else {
            Node<T> previousNode = node(index - 1);
            Node<T> nextNode = previousNode.next;
            Node<T> newNode = new Node(value);
            previousNode.next = newNode;
            newNode.next = nextNode;
            size++;

            if (newNode.next == null) {
                tail = newNode;
            }
        }
    }

그냥 add와 다르게 특정 위치에 노드를 삽입하는 것이다.

• index가 0인 것은 처음 위치에 삽입한다는 것과 같다. addFirst 메소드를 호출한다
• 그렇지 않으면 삽입하고자 하는 위치의 이전노드와 다음노드를 알아야한다.
• 그냥 삽입하게 된다면 다음 노드의 주소를 잃어버려서 참조할 수 없게 된다.
• 위에서 만든 node 메소드를 통해서 이전 노드를 가져온다. 이후 이 node를 통해서 다음 node의 값도 알 수 있다.
• 이전 노드는 새로운 노드를 참조하게 한다. 이후 연결이 끊어지면 안되기 때문에 새로운 노드는 nextNode를 가르키게 한다.
• 새로운 노드의 다음 노드가 null이라는 것은 마지막 노드라는 것이기 때문에 tail을 newNode를 참조하게 한다.

 

[삭제] removeFirst(), removeLast(), remove(int index)

 

int removeFirst()

    public T removeFirst() {
        Node<T> tmp = head;
        head = head.next;
        T returnData = tmp.data;
        tmp = null;
        size--;
        return returnData;
    }

맨 앞의 요소를 그냥 삭제한다면 이후 연결된 노드들의 주소를 잃어버리기 때문에 바로 삭제하면 안된다.

• Node<T> tmp = head : tmp에 head 정보를 우선 담아놓는다
• head는 이제 삭제할 것이기 때문에 head 이후의 노드를 참조하게 한다
• returnData : 삭제해도 안전하기 때문에 삭제한 값을 담는다
• tmp 노드는 필요없기 때문에 null로 바꾼다

T remove(int index)

   public T remove(int index) {
        if (index == 0) {
            return removeFirst();
        }
        Node<T> tmp = node(index - 1);
        Node<T> deleteNode = tmp.next;
        tmp.next = tmp.next.next;
        T returnData = deleteNode.data;

        if (deleteNode == tail) {
            tail = tmp;
        }

        deleteNode = null;
        size--;
        return returnData;
    }

• index = 0은 첫 요소를 삭제하는 것이기 때문에 removeFirst 메소드를 사용한다
• 삽입과 마찬가지로 특정 위치에 있는 노드를 삭제하기 전에는 이전 노드를 알아야한다.
• Node<T> tmp : node(index-1) 메소드를 호출하면 삭제하고자 하는 노드의 이전 노드가 반환된다.
• Node<T> deleteNode : 삭제할 노드는 이전 노드의 다음노드이다. (tmp가 이전 노드를 반환했으니 tmp.next는 삭제할 노드)
• tmp.next = tmp.next.next : 노드를 삭제하면 이전 노드는 삭제하고자 하는 노드의 다음 노드를 가르키게 해야한다. 그렇지 않고 삭제하면 이전 노드부터 연결이 끊어지기 때문이다. tmp.next를 삭제하고자 하는 다다음 노드를 가르키게 하면 삭제해도 된다.

T removeLast() 

    public T removeLast() {
        return remove(size - 1);
    }

마지막 요소를 삭제하는 것은 size - 1번째 인덱스를 삭제하는 것과 같다

 

[읽기] get(int index), indexOf(T value)

 

T get(int index)

    public T get(int index) {
        Node<T> tmp = node(index);
        return tmp.data;
    }

앞서 작성한 node 메소드를 사용하면 해당 인덱스의 노드를 반환하기 때문에 바로 해당 노드.data를 통해서 값을 읽을 수 있다.

 

T indexOf(T value)

    public int indexOf(T value) {
        Node<T> tmp = head;
        int index = 0;
        while (tmp.data != value) {
            tmp = tmp.next;
            index++;
            if (tmp == null) {
                return -1;
            }
        }
        return index;
    }

우선 탐색을 위해서는 무조건 첫번째 노드를 알아야한다.

head 노드 부터 시작하고 index 변수를 사용하여 몇번째 인덱스에 위치하고 있는지 확인한다.

 

toString()

    public String toString() {
        if (head == null) {
            return "No Elements";
        }
        Node<T> temp = head;
        StringBuilder str = new StringBuilder();

        while (temp.next != null) {
            str.append(temp.data + " -> ");
            temp = temp.next;
        }
        str.append(temp.data);
        return str.toString();
    }

테스트를 위해 작성

 

실제 확인해보기

    public static void main(String[] args) {
        MyLinkedList ml = new MyLinkedList();
        ml.addFirst(1);
        ml.add(2);
        ml.add(3);
        ml.addLast(4);
        System.out.println("ml.toString() = " + ml.toString());
        System.out.println();

        ml.addFirst(0);
        ml.addLast(5);
        System.out.println("ml.toString() = " + ml.toString());
        System.out.println();

        ml.add(3, 100);
        System.out.println("ml.toString() = " + ml.toString());
        System.out.println();

        ml.removeFirst();
        System.out.println("removeFirst() = " + ml.toString());

        ml.removeLast();
        System.out.println("removeLast() = " + ml.toString());

        ml.remove(3);
        System.out.println("ml.remove(3) = " + ml.toString());

        System.out.println("ml.get(3) = " + ml.get(3));
        System.out.println("ml.indexOf(5) = " + ml.indexOf(5));
    }

ml.toString() = 1 -> 2 -> 3 -> 4
ml.toString() = 0 -> 1 -> 2 -> 3 -> 4 -> 5
ml.toString() = 0 -> 1 -> 2 -> 100 -> 3 -> 4 -> 5
removeFirst() = 1 -> 2 -> 100 -> 3 -> 4 -> 5
removeLast() = 1 -> 2 -> 100 -> 3 -> 4
ml.remove(3) = 1 -> 2 -> 100 -> 4
ml.get(3) = 4
ml.indexOf(5) = -1

 

전체코드

package datastructure;

public class MyLinkedList<T> {
    private Node<T> head;
    private Node<T> tail;
    private int size;

    private class Node<T> {
        private T data;
        private Node next;

        public Node(T value) {
            this.data = value;
            this.next = null;
        }

        @Override
        public String toString() {
            return String.valueOf(this.data);
        }
    }

    public void addFirst(T value) {
        Node<T> newNode = new Node<>(value);
        newNode.next = head;
        head = newNode;
        size++;

        if (head.next == null) {
            tail = head;
        }
    }

    public void addLast(T value) {
        Node<T> newNode = new Node<T>(value);

        if (size == 0) {
            addFirst(value);
        }
        else {
            tail.next = newNode;
            tail = newNode;
            size++;
        }
    }

    public boolean add(T value) {
        addLast(value);
        return true;
    }

    private Node<T> node(int index) {
        Node<T> x = head;
        for (int i=0; i<index; i++) {
            x = x.next;
        }
        return x;
    }

    public void add(int index, T value) {
        if (index == 0) {
            addFirst(value);
        }
        else {
            Node<T> previousNode = node(index - 1);
            Node<T> nextNode = previousNode.next;
            Node<T> newNode = new Node(value);
            previousNode.next = newNode;
            newNode.next = nextNode;
            size++;

            if (newNode.next == null) {
                tail = newNode;
            }
        }
    }

    public T removeFirst() {
        Node<T> tmp = head;
        head = head.next;
        T returnData = tmp.data;
        tmp = null;
        size--;
        return returnData;
    }

    public T remove(int index) {
        if (index == 0) {
            return removeFirst();
        }
        Node<T> tmp = node(index - 1);
        Node<T> deleteNode = tmp.next;
        tmp.next = tmp.next.next;
        T returnData = deleteNode.data;

        if (deleteNode == tail) {
            tail = tmp;
        }

        deleteNode = null;
        size--;
        return returnData;
    }

    public T removeLast() {
        return remove(size - 1);
    }

    public int size() {
        return size;
    }

    public T get(int index) {
        Node<T> tmp = node(index);
        return tmp.data;
    }

    public int indexOf(T value) {
        Node<T> tmp = head;
        int index = 0;
        while (tmp.data != value) {
            tmp = tmp.next;
            index++;
            if (tmp == null) {
                return -1;
            }
        }
        return index;
    }


    public String toString() {
        if (head == null) {
            return "No Elements";
        }
        Node<T> temp = head;
        StringBuilder str = new StringBuilder();

        while (temp.next != null) {
            str.append(temp.data + " -> ");
            temp = temp.next;
        }
        str.append(temp.data);
        return str.toString();
    }

    public static void main(String[] args) {
        MyLinkedList ml = new MyLinkedList();
        ml.addFirst(1);
        ml.add(2);
        ml.add(3);
        ml.addLast(4);
        System.out.println("ml.toString() = " + ml.toString());
        System.out.println();

        ml.addFirst(0);
        ml.addLast(5);
        System.out.println("ml.toString() = " + ml.toString());
        System.out.println();

        ml.add(3, 100);
        System.out.println("ml.toString() = " + ml.toString());
        System.out.println();

        ml.removeFirst();
        System.out.println("removeFirst() = " + ml.toString());

        ml.removeLast();
        System.out.println("removeLast() = " + ml.toString());

        ml.remove(3);
        System.out.println("ml.remove(3) = " + ml.toString());

        System.out.println("ml.get(3) = " + ml.get(3));
        System.out.println("ml.indexOf(5) = " + ml.indexOf(5));
    }
}