Java로 자료구조(LinkedList, Stack, Queue) 구현해보기

알고리즘 공부에 앞서서 기본기를 다진다는 느낌으로 자료구조를 직접 구현해보려고 한다.

언어는 자바로 구현할 것이며 내부함수들을 참고하여 만들어 보도록 하겠다.

크게 세가지의 자료구조를 구현해볼 것이고, 다른 자료구조도 필요성을 느끼게 된다면 나중에 추가하도록 하겠다.

1. LinkedList

핵심적인 메서드들만 추려서 구현해보았다.

package linked;

abstract class AbstractLinked
{
    abstract void clear();
    abstract void add(Object element);
    abstract void add(int position, Object element);
    abstract void addFirst(Object element);
    abstract void addLast(Object element);
    abstract void remove(int position);
    abstract Object get(int position);
    abstract int size();
}

 

Node객체에는 값을 의미하는 data 멤버와 다음 레퍼런스를 검색할 수 있게 도와주는 next 멤버를 가지고 있다.

class Node
{
    private Object data;
    Node next;

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

    public Object getData()
    {
        return data;
    }

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

 

MyLinkedList 클래스에는 처음을 뜻하는 head 노드와, 끝을 뜻하는 tail 노드가 있다.

package linked;


public class MyLinkedList extends AbstractLinked
{
    private Node head;
    private Node tail;
    private int listSize = 0;


    @Override
    void clear()
    {
        head = null;
        tail = null;
        listSize = 0;
    }

    @Override
    void add(Object element)
    {
        addLast(element);
    }

    @Override
    void add(int position, Object element)
    {
        isCheckException(position);
        if (position == 0)
        {
            addFirst(element);
            return;
        }

        Node newNode = new Node(element);

        Node prevNode = getNode(position-1);
        newNode.next = prevNode.next;
        prevNode.next = newNode;
        if (newNode.next == null)
        {
            tail = newNode;
        }
        listSize++;
    }

    @Override
    void addFirst(Object element)
    {
        Node newNode = new Node(element);
        if (head == null)
        {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
        if (head.next == null)
        {
            tail = newNode;
        }
        listSize++;
    }

    @Override
    void addLast(Object element)
    {
        isCheckException();
        if (listSize == 0)
        {
            addFirst(element);
            return;
        }
        Node newNode = new Node(element);
        tail.next = newNode;
        tail = newNode;
        listSize++;
    }

    @Override
    void remove(int position)
    {
        isCheckException(position);

        Node rvNode = getNode(position);
        if (position == 0)
        {
            head = head.next;
        } else {
            Node prevNode = getNode(position-1);
            prevNode.next = rvNode.next;
            if (prevNode.next == null)
            {
                tail = prevNode;
            }
        }
        listSize--;
    }

    @Override
    Object get(int position)
    {
        isCheckException(position);
        return getNode(position).getData();
    }

    @Override
    int size()
    {
        return listSize;
    }

    @Override
    public String toString()
    {
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        for (int i = 0; i<size(); i++)
        {
            builder.append(get(i).toString());
            if (i != size()-1)
            {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.toString();
    }

    private Node getNode(int position)
    {
        isCheckException(position);
        if (position == 0)
        {
            return head;
        }
        Node node = head;
        for (int i = 0; i<position; i++)
        {
            node = node.next;
        }
        return node;
    }

    private void isCheckException(int position)
    {
        if (size() < 0 || size() < position || position < 0)
        {
            throw new IndexOutOfBoundsException();
        }
    }
    private void isCheckException()
    {
        if (size() < 0)
        {
            throw new IndexOutOfBoundsException();
        }
    }
}

 

메인클래스

package linked;

public class LinkedListExample
{
    public static void main(String [] args)
    {
        MyLinkedList mylist = new MyLinkedList();
        for (int i = 0; i < 10; i++)
        {
            mylist.add(i);
        }

        mylist.add(8, 100);
        mylist.add(3, 100);

        System.out.println(mylist.toString());

        mylist.remove(8);
        mylist.remove(3);

        System.out.println(mylist.toString());

        mylist.clear();

        System.out.println(mylist.toString());
    }
}

2. Stack

다른 블로그들을 보니 Stack을 리스트로 구현을 많이 하던데 여기서는 Node 객체로 구현해보겠다.

먼저 주요 함수들을 지정했다.

abstract class AbstractStack
{
    public abstract void clear();
    public abstract Object push(Object element);
    public abstract Object pop();
    public abstract Object peek();
    public abstract boolean empty();
    public abstract int search(Object element);
}

 

Node는 LinkedList에서 사용한 것을 그대로 복사해왔다.

package stack;


class Node
{
    private Object data;
    Node next;

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

    public Object getData()
    {
        return data;
    }

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

 

MyStack 클래스에서는 top 노드만 가지고 있으면 Stack을 구현할 수 있다.

package stack;

import linked.MyLinkedList;

import java.util.EmptyStackException;

public class MyStack extends AbstractStack
{
    private Node top;

    @Override
    public void clear()
    {
        top = null;
    }

    @Override
    public Object push(Object element)
    {
        Node newNode = new Node(element);
        newNode.next = top;
        top = newNode;
        return element;
    }

    @Override
    public Object pop()
    {
        if (top == null)
        {
            throw new EmptyStackException();
        }
        Node temp = top;
        top = top.next;
        return temp.getData();
    }

    @Override
    public Object peek()
    {
        if (top == null)
        {
            throw new EmptyStackException();
        }
        return top.getData();
    }

    @Override
    public boolean empty()
    {
        return top == null;
    }

    @Override
    public int search(Object element)
    {
        if (top == null)
        {
            throw new EmptyStackException();
        }
        int i = 1;
        Node temp = top;
        while (temp != null)
        {
            if (temp.getData().equals(element))
            {
                return i;
            }
            temp = temp.next;
            i++;
        }
        return -1;
    }

    @Override
    public String toString()
    {
        MyLinkedList myList = new MyLinkedList();

        Node temp = top;
        while (temp != null)
        {
            myList.addFirst(temp.getData());
            temp = temp.next;
        }
        return myList.toString();
    }
}

 

메인 클래스

package stack;

import java.util.Stack;

public class StackExample
{
    public static void main(String [] args)
    {
        Stack<String> stack = new Stack<>();
        MyStack myStack = new MyStack();
        for (int i = 1; i <= 5; i++)
        {
            stack.push(String.valueOf(i));
            myStack.push(String.valueOf(i));
        }
        System.out.println(stack.empty());
        System.out.println(stack.peek());
        System.out.println(stack);
        System.out.println(stack.pop());
        System.out.println(stack);
        System.out.println(stack.search("6"));
        System.out.println(stack.search("1"));
        stack.clear();
        System.out.println(stack);

        System.out.println();
        System.out.println();

        System.out.println(myStack.empty());
        System.out.println(myStack.peek());
        System.out.println(myStack);
        System.out.println(myStack.pop());
        System.out.println(myStack);
        System.out.println(myStack.search("6"));
        System.out.println(myStack.search("1"));
        myStack.clear();
        System.out.println(myStack);
    }
}

내부함수와 같은 결과가 나오는 것을 확인 할 수 있다.

3. Queue

큐도 노드로 구현하면 비슷비슷하다.

주요 함수 ㄱㄱ

package data.structure.queue;

abstract class AbstractQueue
{
    abstract public void offer(Object element);
    abstract public Object remove();
    abstract public Object poll();
    abstract public Object peek();
}

package data.structure.queue;


class Node
{
    private Object data;
    Node next;

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

    public Object getData()
    {
        return data;
    }

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

package data.structure.queue;

import data.structure.linked.MyLinkedList;

import java.util.NoSuchElementException;

public class Myqueue extends AbstractQueue
{
    private Node first;

    @Override
    public void offer(Object element)
    {
        Node newNode = new Node(element);
        if (first == null)
        {
            first = newNode;
            return;
        }

        Node temp = first;
        while (true)
        {
            if (temp.next == null)
            {
                temp.next = newNode;
                break;
            } else {
                temp = temp.next;
            }
        }
    }

    @Override
    public Object remove()
    {
        if (first == null)
        {
            return null;
        }
        Object data = first.getData();
        first = first.next;
        return data;
    }

    @Override
    public Object poll()
    {
        if (first == null)
        {
            throw new NoSuchElementException();
        }
        Object data = first.getData();
        first = first.next;
        return data;
    }

    @Override
    public Object peek()
    {
        if (first == null)
        {
            return null;
        }
        return first.getData();
    }

    @Override
    public String toString()
    {
        MyLinkedList myList = new MyLinkedList();

        Node temp = first;
        while (temp != null)
        {
            myList.add(temp.getData());
            temp = temp.next;
        }
        return myList.toString();
    }
}

 메인 클래스

package data.structure.queue;

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample
{
    public static void main(String [] args)
    {
        Queue<String> queue = new LinkedList<>();
        Myqueue myqueue = new Myqueue();

        for (int i = 0; i<5; i++)
        {
            queue.offer(String.valueOf(i));
            myqueue.offer(String.valueOf(i));
        }

        System.out.println(queue);
        System.out.println(queue.peek());
        System.out.println(queue.poll());
        System.out.println(queue);
        System.out.println(queue.remove());
        System.out.println(queue);


        System.out.println();
        System.out.println();


        System.out.println(myqueue);
        System.out.println(myqueue.peek());
        System.out.println(myqueue.poll());
        System.out.println(myqueue);
        System.out.println(myqueue.remove());
        System.out.println(myqueue);
    }
}