ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Java - LinkedList, Stack, Queue 구현하기
    Java/java study 2022. 1. 2. 02:26
    728x90
    반응형
    • 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;
      }
    }
    728x90
    반응형

    'Java > java study' 카테고리의 다른 글

    Java - 메서드 오버로딩과 오버라이딩  (0) 2022.01.09
    Java - 클래스(Class) 와 객체 생성  (0) 2022.01.09
    JUnit 5  (0) 2022.01.02
    Java - 제어문  (0) 2022.01.01
    Java - 연산자  (0) 2021.12.19

    댓글

Designed by Tistory.