Java - LinkedList, Stack, Queue 구현하기

• LinkedList 구현
• Stack 구현
• 구현한 LinkedList로 Stack 구현
• Queue 구현

 

LinkedList 구현

 LinkedList 란?

• Collection 프레임 워크의 일부이며 Java.util 패키지에 소속되어 있다.
• LinkedList는 데이터가 연속된 위치에 저장되어 있지 않다.
• 데이터를 담고 있는 노드들이 연결되어있으며 노드의 포인터가 이전, 다음 노드와의 연결을 담당한다.
• 배열에서 자주 삽입, 삭제가 이루어지는 경우 용이하여 ArrayList보다 선호된다.
• ArrayList보다 검색에 있어서는 느리다.
• 리스트의 종류로 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다.

 

public class ListNode {
    int data;
    ListNode next;

    public ListNode() {}
    public ListNode(int data) {
        this.data = data;
        this.next = null;
    }

    public ListNode add(ListNode head, ListNode nodeToAdd, int position) {
        ListNode node = head;

        for (int i = 0; i < position - 1; i++) {
            node = node.next;
        }

        nodeToAdd.next = node.next;
        node.next = nodeToAdd;
        return head;
    }

    public ListNode remove(ListNode head, int positionToRemove) {
        ListNode node = head;
				
        if(positionToRemove == 0){
            ListNode deleteToNode = node;
            head = node.next;
            deleteToNode.next = null;
            return deleteToNode;
        }
        for (int i = 0; i < positionToRemove - 1; i++) {
            node = node.next;
        }
				
        ListNode deleteToNode = node.next;
        node.next = deleteToNode.next;
        deleteToNode.next = null;
        return deleteToNode;
    }

    public boolean contains(ListNode head, ListNode nodeToCheck) {
        while (head.next != null) {
            if (head.next == nodeToCheck)
                return true;
            head = head.next;
        }
        return false;
    }
}

---

Stack 구현

 Stack 이란?

 스택은 메모리 안 데이터들을 더욱 효율적으로 다루기 위해 만들어진 데이터 참조 방식이며, 한쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형구조이다. 즉, 마지막에 들어온 데이터가 가장 먼저 나가는 특징인 LIFO구조(Last In First Out, 후입 선출)를 갖는다.

 

public class ArrayStack {
    int[] stack;
    int top;

    public ArrayStack(int size) {
        stack = new int[size];
        top = -1;
    }

    public void push(int data) {
        stack[++top] = data;
    }

    public int pop() {
        if(top == -1){
            System.out.println("Empty");
            return top;
        }
        return stack[top--];
    }
}

 

---

ListNode를 이용하여 Stack을 구현

public class ListNodeStack {

    static int top;
    ListNode node;
    public ListNodeStack() {
        this.node = null;
        this.top = -1;
    }

    public void push(int data) {
        ListNode pushNode = new ListNode(data);
        if(node == null){
            node = new ListNode(data);
            top++;
        }else {
            node = node.add(node, pushNode, ++top);
        }
    }

    public int pop() {
        if(top == -1) {
            System.out.println("Empty");
            return top;
        }
        return node.remove(node,top--).data;
    }
}

---

Queue 구현

배열을 이용한 Queue 구현

package javastudy5;

public class ArrayQueue {
    int MAX = 1000;
    int head;
    int tail;
    int [] queue;
    public ArrayQueue() {
        head = tail = 0;
        queue = new int[MAX]; 
    }

    public boolean queueisEmpty() { 
        return head == tail;
    }
    public boolean queueisFull() {
        if(tail == MAX-1) {
            return true;
        }else 
            return false;
    }
    public int size() {
        return head-tail;
    }
    public void push(int value) {
        if(queueisFull()) {
            System.out.println("Queue is Full");
            return;
        }
        queue[tail++] = value;
    }
    public int pop() {
        if(queueisEmpty()) {
            System.out.println("Queue is Empty");
            return -1;
        }
        int popValue = queue[head++];
        return popValue;
    }
    public int peek() {
        if(queueisEmpty()) {
            System.out.println("Queue is Empty");
            return -1;
        }
        int popValue = queue[head];
        return popValue;
    }
}

 

 

ListNode를 이용한 Queue 구현

public class ListNodeQueue {
  ListNode head;

  public ListNodeQueue() {
    this.head = new ListNode();
  }

  public void push(int data) {
    ListNode node = new ListNode(data);
    ListNode cur = this.head;
    while (cur.next != null) cur = cur.next;
    cur.next = node;
  }

  public int pop() {
    int data = this.head.next.elements;
    this.head = this.head.next;
    return data;
  }
}