자료구조 - LinkedList

링크드 리스트

연결 리스트라고 한다. 배열하고의 차이점으로 순차적으로 연결된 공간에 나열하는 구조라면, 링크드 리스트는 떨어진 곳에 데이터를 화살표로 연결하여 관리하는 구조이다.

말 그대로 가장 큰 특징은 포인터라는 개념이다. 아래 코드르 보며 이해를 해보자.

 

생성자 구현

기본적으로 node라는 객체를 연결해 주는 코드를 만들 것이다.

private Node head;
    public MyLinkedList() {
        this.size = 0;
        this.head = null; // dummy head node
    }

 

Node 구현

링크드 리스트안에 구현을 했지만 따로 구현해도 크게 문제가 없다.

private class Node {
        T data;
        Node next;
        Node(T data) {
            this.data = data;
        }

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

데이터를 필드로 선언하였으며, 포인터를 next로 줌으로써 다음 node를 가리키는 포인터를 구현해줬다.

 

기능 구현

추가, 제거, 삽입 등 다양한 기능을 만들어 보았다.
코드는 아래와 같다.

@Override
    public void add(T t) {
        Node curr = this.head;

        while (curr.next != null) {
            curr = curr.next;
        }

        Node node = new Node(t);
        curr.next = node;
        this.size++;
    }

    @Override
    public void insert(int index, T t) {
        if (index > this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

        Node prev = this.head;
        Node curr = prev.next;

        int i = 0;

        while (i++ < index) {
            prev = prev.next;
            curr = curr.next;
        }

        Node node = new Node(t, curr);
        prev.next = node;
        this.size++;

    }

    @Override
    public void clear() {
        this.size = 0;
        this.head.next = null;
    }

    @Override
    public boolean delete(T t) {
        Node prev = this.head;
        Node curr=  prev.next;

        while (curr.next != null) {
            if (curr.data.equals(t)) {
                prev.next = curr.next;
                curr.next = null;
                this.size--;
                return true;
            }
            prev = prev.next;
            curr = curr.next;
        }
        return false;
    }

    @Override
    public int deleteByIndex(int index) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

        Node prev = this.head;
        Node curr = prev.next;

        int i = 0;
        while (i++ < index) {
            prev = prev.next;
            curr = curr.next;
        }

        prev.next = curr.next;
        curr.next = null;
        this.size--;
        return i;
    }

    @Override
    public T get(int index) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

        Node curr = this.head;
        int i = -1;
        while (i++ < index) {
            curr = curr.next;
        }
        return curr.data;
    }

    @Override
    public int indexOf(T t) {
        Node curr = this.head;
        int index = -1;

        while (curr != null) {
            if (t.equals(curr.data)) {
                return index;
            }
            curr = curr.next;
            index++;
        }
        return -1;
    }

    @Override
    public boolean isEmpty() {
        return this.head.next == null;
    }

    @Override
    public boolean contains(T t) {
        Node curr = this.head.next;
        while (curr != null) {
            if (t.equals(curr.data)) {
                return true;
            }
            curr = curr.next;
        }
        return false;
    }

    @Override
    public int size() {
        return this.size;
    }