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