[Data Structure] 연결 리스트 (LinkedList)개념 및 구현

연결 리스트(LinkedList)

LinkedList는 선형으로 그룹화된 데이터의 집합으로 데이터와 다음 데이터의 주소를 포함하고 있는 노드들을 선형으로 연결한 자료구조이다.

 

배열을 기반으로 사용하는 ArrayList는 연속된 공간 안에 메모리를 차지해서 데이터를 읽고 쓸 수 있다. 배열의 크기만큼 메모리를 할당해서 사용하기 때문에 데이터가 배열의 크기보다 많아지면 데이터를 새로 할당하고 추가/삭제 연산은 각 데이터를 앞으로 당기거나 뒤로 밀어야 한다. 

 

반면 노드를 기반으로 한 LinkedList는 연속된 공간이 아니라 메모리 상에 흩어져 있는 노드들을 연결한 자료구조이기 때문에 데이터의 추가 삭제는 ArrayList보다 빠르게 연산할 수 있지만 특정 데이터를 찾는 연산은 노드를 하나하나 참조하여 찾아야 하기 때문에 상대적으로 느리다. 

연결 리스트의 특징

1. 데이터의 추가 삭제 연산이 빠르다.

연결 리스트의 데이터 추가 삭제는 노드의 참조값만 변경하기 때문에 ArrayList에 비해 상대적으로 빠르다.

 

2. 데이터를 찾기 위해 노드 전체를 조회해야 한다. 

인덱스로 접근하는 ArrayList와 달리 리스트의 head부터 tail까지 순회하며 찾아야 하기 때문에 상대적으로 느리다.

 

---

연결 리스트 주요 메서드 및 구현

참고
https://opentutorials.org/module/1335/8857

addFirst() - 연결 리스트의 제일 앞에 데이터 추가
addLast() - 연결 리스트의 제일 뒤에 데이터 추가
add()        - 연결 리스트의 특정 인덱스에 데이터 추가
removeFirst() - 연결 리스트의 제일 앞 노드 제거
removeLast() - 연결 리스트의 제일 뒷 노드 제거
remove()        - 연결 리스트의 특정 인덱스 노드 제거
isEmpty() - 연결 리스트가 비어있는지 boolean으로 반환
clear()      - 연결 리스트의 모든 노드 제거
size()       - 연결 리스트의 노드 개수 반환 

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

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

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }
}

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

    public MyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public void addFirst(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.setNext(head);
        head = newNode;
        size++;
        if (head.getNext() == null) {
            tail = head;
        }
    }

    public void addLast(T data) {
        if (size == 0) {
            addFirst(data);
        } else {
            Node<T> newNode = new Node<>(data);
            tail.setNext(newNode);
            tail = newNode;
            size++;
        }
    }

    public void add(int index, T data) {
        if (index > size || index < 0) {
            System.out.println("add() 인덱스 에러!!");
            return;
        }
        if (index == size) {
            addLast(data);
        } else if (index == 0) {
            addFirst(data);
        } else {
            Node<T> prevNode = getNthNode(index - 1);
            Node<T> nextNode = prevNode.getNext();
            Node<T> newNode = new Node<>(data);

            prevNode.setNext(newNode);
            newNode.setNext(nextNode);
            size++;
            if (newNode.getNext() == null) {
                tail = newNode;
            }
        }
    }

    public T removeFirst() {
        if (size == 0) {
            return null;
        }
        Node<T> first = head;
        head = first.getNext();

        T data = first.getData();
        first = null;
        size--;
        return data;
    }

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

    public T remove(int index) {
        if (index >= size || index < 0) {
            System.out.println("remove() 인덱스 에러!!");
            return null;
        }
        if (index == 0) {
            return removeFirst();
        }
        Node<T> prevNode = getNthNode(index - 1);
        Node<T> removeNode = prevNode.getNext();

        prevNode.setNext(removeNode.getNext());

        T data = removeNode.getData();

        if (removeNode == tail) {
            tail = prevNode;
        }

        removeNode = null;
        size--;

        return data;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        Node<T> temp = head;
        while (temp.getNext() == null) {
            Node<T> next = temp.getNext();
            temp.setNext(null);
            temp.setData(null);

            temp = next;
        }

        head = null;
        tail = null;
        size = 0;
    }

    public String toString() {
        if (head == null) {
            return "[]";
        }

        Node<T> temp = head;
        String str = "[";
        while (temp.getNext() != null) {
            str += temp.getData() + ", ";
            temp = temp.getNext();
        }

        str += temp.getData();
        str += "]";

        return str;
    }

    public T get(int index) {
        if (index >= size || index < 0) {
            System.out.println("get() 인덱스 에러!!");
            return null;
        }
        return getNthNode(index).getData();
    }

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

 

Node 클래스

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

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

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }
}

연결 리스트를 사용하기 위해 노드 클래스를 정의해야 한다. 노드 클래스는 저장될 데이터와 다음 노드를 가리킬 next 변수를 정의한다.

 

MyLinkedList()

public MyLinkedList() {
    this.head = null;
    this.tail = null;
    this.size = 0;
}

연결 리스트의 처음과 끝을 가리킬 head와 tail 그리고 데이터의 개수를 저장할 size 변수가 있다.  인스턴스 생성 시 head와 tail을 null로 초기화한다.

 

addFirst()

public void addFirst(T data) {
    Node<T> newNode = new Node<>(data);
    newNode.setNext(head);
    head = newNode;
    size++;
    if (head.getNext() == null) {
        tail = head;
    }
}

연결 리스트의 제일 앞에 데이터를 담은 노드를 추가한다.

제일 앞에 추가하기 때문에 newNode의 next를 head를 가리키게 하고 head의 위치를 newNode로 변경한다. 리스트가 비어있을 때 추가되었을 경우엔 newNode의 next가 null이기 때문에 tail도 head가 가리키고 있는 newNode를 가리키게 한다.

 

addLast()

public void addLast(T data) {
    if (size == 0) {
        addFirst(data);
    } else {
        Node<T> newNode = new Node<>(data);
        tail.setNext(newNode);
        tail = newNode;
        size++;
    }
}

addFirst와는 반대로 리스트의 가장 마지막에 노드를 추가한다. size가 0인 경우엔 addFirst와 다를 게 없기 때문에 addFirst메서드를 호출한다.

tail의 next가 newNode를 가리키게 하고 tail이 newNode를 가리키게 한다.

 

getNthNode()

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

add나 remove 같은 메서드에서 특정 인덱스의 노드를 가져올 때 내부적으로 사용하기 때문에 접근제어자를 public이 아닌 private으로 만들었다.

 

add()

public void add(int index, T data) {
    if (index > size || index < 0) {
        System.out.println("add() 인덱스 에러!!");
        return;
    }
    if (index == size) {
        addLast(data);
    } else if (index == 0) {
        addFirst(data);
    } else {
        Node<T> prevNode = getNthNode(index - 1);
        Node<T> nextNode = prevNode.getNext();
        Node<T> newNode = new Node<>(data);

        prevNode.setNext(newNode);
        newNode.setNext(nextNode);
        size++;
        if (newNode.getNext() == null) {
            tail = newNode;
        }
    }
}

특정 인덱스에 노드를 추가하는 메서드. index가 size인 경우 가장 마지막에 노드를 추가하기 때문에 addLast메서드를 호출하고 0인 경우 addFirst 메서드를 호출한다. 노드를 다른 노드들 사이에 추가하는 경우엔 해당 인덱스의 앞 노드와 뒷 노드가 필요하다. prevNode의 next를 newNode로 바꾸고 newNode의 next를 nextNode로 설정한다. 

 

removeFirst()

public T removeFirst() {
    if (size == 0) {
        return null;
    }
    Node<T> first = head;
    head = first.getNext();

    T data = first.getData();
    first = null;
    size--;
    return data;
}

가장 앞 노드를 제거하기 위해 head를 head의 다음 노드로 옮기고 노드를 null로 변경한다. 

 

remove()

public T remove(int index) {
    if (index >= size || index < 0) {
        System.out.println("remove() 인덱스 에러!!");
        return null;
    }
    if (index == 0) {
        return removeFirst();
    }
    Node<T> prevNode = getNthNode(index - 1);
    Node<T> removeNode = prevNode.getNext();

    prevNode.setNext(removeNode.getNext());

    T data = removeNode.getData();

    if (removeNode == tail) {
        tail = prevNode;
    }

    removeNode = null;
    size--;

    return data;
}

제거할 노드의 앞 노드를 가져와서 next를 제거할 노드의 next로 변경하고 지워준다. 제거되는 노드가 tail일 경우 prevNode로 옮긴다. 

 

removeLast()

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

마지막 노드를 제거할 땐 remove 메서드를 호출

 

size() & isEmpty()

public int size() {
    return size;
}
    
public boolean isEmpty() {
    return size == 0;
}

 

데이터의 개수와 리스트가 비어있는지 boolean 타입 반환

clear()

public void clear() {
    Node<T> temp = head;
    while (temp.getNext() == null) {
        Node<T> next = temp.getNext();
        temp.setNext(null);
        temp.setData(null);

        temp = next;
    }

    head = null;
    tail = null;
    size = 0;
}

head부터 while문으로 next를 찾아가면서 데이터를 지운 뒤 head와 tail을 null로, size를 0으로 변경한다.

 

get()

public T get(int index) {
    if (index >= size || index < 0) {
        System.out.println("get() 인덱스 에러!!");
        return null;
    }
    return getNthNode(index).getData();
}

노드의 데이터를 반환한다.

 

 

public class Main {
    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();

        System.out.println("list isEmpty()? " + list.isEmpty());
        list.addFirst(1);
        list.add(0,2);
        list.addLast(5);
        System.out.println("list = " + list + " size = " + list.size());
        System.out.println("list isEmpty()? " + list.isEmpty());

        System.out.println("--------------remove-------------- ");
        list.remove(1);
        System.out.println("list = " + list + " size = " + list.size());
        System.out.println("list.get(0) = " + list.get(0));
        list.removeFirst();
        list.removeLast();
        System.out.println("list = " + list + " size = " + list.size());

        System.out.println("--------------clear-------------- ");
        for(int i = 0; i < 5; i++){
            list.addLast(i);
        }
        System.out.println("list = " + list + " size = " + list.size());
        list.clear();
        System.out.println("list = " + list + " size = " + list.size());

    }
}