데이터간에 순서가 보장되지 않음 ex) 2, 3, 4, 1, 5 추가 후 iterator를 이용해 출력 시 1, 2, 4, 3, 5로 출력
구현방법 및 특징 - 배열 기반으로 구현 1) 인덱스로 데이터에 바로 접근할 수 있음 2) 데이터의 삽입/삭제에서 데이터들을 한칸씩 뒤로 밀거나 당기는 연산이 있어야 함 3) 삽입의 위치를 찾아내기 위해 최악의 경우 배열의 모든 데이터들과 우선순위를 비교해야 함 4) 저장 시 시간복잡도 O(n), 삭제 시 시간복잡도 O(1)
- 연결리스트 기반으로 구현 1) 삽입의 위치를 찾기위해 최악의 경우 리스트의 모든 데이터와 우선순위를 비교해야 함 2) 저장 시 시간복잡도 O(n), 삭제 시 시간복잡도 O(n)
- 힙(heap)을 이용한 구현 1) 완전 이진트리의 형태 2) 단말노드에서 루트노드로 갈수록 값이 커지는 것을 최대 힙 (max heap) 이라고 하며 그 반대는 최소 힙 (min heap) 이라고 함 3) 저장 시 시간복잡도 O(logN), 삭제 시 시간복잡도 O(logN)
4) 형제노드끼리의 대소관계는 정해지지 않음
힙의 구현 (최대 힙 기준) 방법
힙도 마찬가지로 배열과 연결리스트로 구현 가능
그러나 배열로 구현하는 것이 일반적 (리스트로 구현할 경우 특정노드에 접근하거나 데이터 저장 시 마지막 위치를 알기 어렵기 때문)
데이터 저장 1) 완전 이진 트리르 ㄹ만족하는 마지막 위치에 데이터 저장 2) 부모노드와 대소관계 비교 후 부모노드의 값이 더 클 경우 교환하는 과정을 반복 (최대 힙 기준) 3) 아래는 데이터 10, 5, 7, 1 순으로 저장된 트리에 8을 저장한 그림
데이터 삭제 1) 데이터의 루트노드 삭제 2) 루트노드의 빈 공간은 마지막 노드를 루트노드로 설정 3) 자식노드들과 비교하며 더 큰 자식노드와 교환
노드마다 인덱스 값 부여
구현의 편의 상 인덱스는 1번부터 적용
노드의 인덱스 값 구하기 - 완전 이진 트리의 특성 때문에 아래와 같이 수식화 할 수 있음 - 아래 수식의 결과값들은 모두 정수 형태 (5 / 2 => 2) 1) 왼쪽 자식노드의 인덱스 값 : 부모노드의 인덱스 값 * 2 2) 오른쪽 자식노드의 인덱스 값 : 부모노드의 인덱스 값 * 2 + 1 3) 부모노드의 인덱스 값 : 자식노드의 인덱스 값 / 2
힙 구현
추상자료형 (ADT)
자료형
반환값
내용
Initialize()
void
힙 초기화
initialize(comparator)
void
힙 초기화 (비교함수 외부 등록)
isEmpty()
boolean
힙이 비어있는지 확인
compareHighChild(index)
int
자식노드 중 누가 더 우선순위가 높은지 반환
add(Data)
void
힙에 데이터 추가
remove()
Data
데이터 삭제
getParent(index)
int
부모노드의 위치값 반환
getLChild(index)
int
왼쪽 자식노드의 위치값 반환
getRChild(index)
int
오른쪽 자식노드의 위치값 반환
핵심기능 - 데이터 추가 : 마지막 위치에 데이터를 저장한 후 부모노드와 우선순위를 비교해서 자신이 어디에 위치해야 하는지 찾음 - 데이터 삭제 : 힙의 루트노드를 지우고 그 위치에 마지막 노드를 올린 후 자식노드와 비교하며 자신이 어디에 위치해야 하는지 찾음
구현
[ArrayHeap.java]
package Heap.ArrayList;
import java.util.Comparator;
public class ArrayHeap<E> {
private int MAX_CAPACITY = 5;
// 외부에서 정렬 방법 설정을 위한 변수
private Comparator<? super E> comparator = null;
// 내부에서 사용할 정렬을 위한 변수
private Comparable<? super E> comp = null;
private Object[] heap = null;
private int dataCount = 0;
public void init(int capacity) {
MAX_CAPACITY = capacity;
heap = new Object[MAX_CAPACITY + 1];
dataCount = 0;
}
public void init(int capacity, Comparator<? super E> comparator){
MAX_CAPACITY = capacity;
heap = new Object[MAX_CAPACITY + 1];
dataCount = 0;
this.comparator = comparator;
}
// index의 두 개의 자식 중 더 높은 놈 반환
private int compareHighChild(int index) {
// 자식이 없을 때
if (getLChild(index) > dataCount) {
return 0;
}
// 자식이 한 개
// 이진트리이므로 왼쪽부터 채워지기 때문에 왼쪽 자식노드만 확인
else if (getLChild(index) == dataCount) {
return getLChild(index);
}
// 자식이 두 개
else {
int lChild = getLChild(index);
int rChild = getRChild(index);
if (comparator == null) {
comp = (Comparable<? super E>)heap[lChild];
if (comp.compareTo((E)heap[rChild]) < 0) {
return lChild;
}
else {
return rChild;
}
}
else {
if (comparator.compare((E) heap[lChild], (E) heap[rChild]) < 0) {
return lChild;
}
else {
return rChild;
}
}
}
}
public boolean isEmpty() {
if (dataCount == 0){
return true;
}
return false;
}
// 마지막 위치에 데이터를 저장한 후 부모노드와 우선순위를 비교해서 자신이 어디에 위치해야 하는지 찾음
public void add(E data) {
if (dataCount > MAX_CAPACITY) {
System.out.println("저장 공간이 부족합니다.");
return;
}
int index = dataCount + 1;
while (index != 1){
if (comparator == null) {
// 부모노드와 우선순위 비교
comp = (Comparable<? super E>) data;
// 자식노드의 우선순위가 더 낮은 경우
if (comp.compareTo((E)heap[getParent(index)]) >= 0){
break;
}
}
else {
// 부모노드와 우선순위 비교
// 자식노드의 우선순위가 더 낮은 경우
if (comparator.compare(data, (E)heap[getParent(index)]) >= 0){
break;
}
}
// 자식노드가 더 우선순위가 높으므로 부모노드를 자식노드와 swap함
heap[index] = heap[getParent(index)];
index = getParent(index);
}
dataCount++;
heap[index] = data;
}
// 힙의 루트노드를 지우고 그 위치에 마지막 노드를 올린 후 자식노드와 비교하며 자신이 어디에 위치해야 하는지 찾음
public E remove() {
E removeData = (E)heap[1];
heap[1] = null;
int lastIndex = dataCount;
int childIndex = 0;
int parentIndex = 1;
while((childIndex = compareHighChild(parentIndex)) > 0) {
if (comparator == null) {
comp = (Comparable<? super E>)heap[lastIndex];
if (comp.compareTo((E)heap[childIndex]) < 0){
break;
}
}
else {
if (comparator.compare((E)heap[lastIndex], (E)heap[childIndex]) < 0){
break;
}
}
heap[parentIndex] = heap[childIndex];
parentIndex = childIndex;
}
heap[parentIndex] = heap[lastIndex];
heap[lastIndex] = null;
dataCount--;
return removeData;
}
private int getParent(int index) {
return index / 2;
}
private int getLChild(int index) {
return index * 2;
}
private int getRChild(int index) {
return index * 2 + 1;
}
public void printAll() {
for(E e : (E[])heap) {
if (e == null) {
continue;
}
System.out.println(e);
}
}
}
package BinaryTree.LinkedList;
public class BinaryTreeMain {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
BTreeNode node1 = binaryTree.createBTreeNode();
BTreeNode node2 = binaryTree.createBTreeNode();
BTreeNode node3 = binaryTree.createBTreeNode();
BTreeNode node4 = binaryTree.createBTreeNode();
BTreeNode node5 = binaryTree.createBTreeNode();
binaryTree.setData(node1, 'A');
binaryTree.setData(node2, 'B');
binaryTree.setData(node3, 'C');
binaryTree.setData(node4, 'D');
binaryTree.setData(node5, 'E');
binaryTree.createLeftSubTree(node1, node2); // B를 A의 왼쪽 서브트리로 등록
binaryTree.createRightSubTree(node1, node3); // C를 A의 오른쪽 서브트리로 등록
binaryTree.createLeftSubTree(node2, node4); // D를 B의 왼쪽 서브트리로 등록
binaryTree.createRightSubTree(node2, node5); // E를 B의 오른쪽 서브트리로 등록
BTreeNode tmpNode = null;
System.out.println(binaryTree.getData(node1)); // 루트 노드 데이터 반환
tmpNode = binaryTree.getLeftSubTree(node1);
System.out.println(binaryTree.getData(tmpNode)); // A의 왼쪽 서브트리 데이터 반환
tmpNode = binaryTree.getRightSubTree(node1);
System.out.println(binaryTree.getData(tmpNode)); // A의 오른쪽 서브트리 데이터 반환
tmpNode = binaryTree.getLeftSubTree(node2);
System.out.println(binaryTree.getData(tmpNode)); // B의 왼쪽 서브트리 데이터 반환
tmpNode = binaryTree.getRightSubTree(node2);
System.out.println(binaryTree.getData(tmpNode)); // B의 오른쪽 서브트리 데이터 반환
}
}
결과
이진트리의 순회
전위순회 (Preorder Traversal) : 루트 노드를 먼저 순회
중위순회 (Inorder Traversal) : 루트 노드를 중간에 순회
후위순회 (Postorder Traversal) : 루트 노드를 마지막에 순회
중위순회 방법 - 재귀적으로 순회 가능
1) 왼쪽 서브트리 순회 2) 루트 노드 방문 3) 오른쪽 서브트리 순회
중위순회 구현
// 중위 순회
void InorderTraverse(BTreeNode node) {
if (node == null){
return;
}
InorderTraverse(node.leftNode);
System.out.println(node.data);
InorderTraverse(node.rightNode);
}
전위순회 및 후위순회 - 중위순회의 방법 1, 2, 3의 순서를 변경 - 중위순회
// 전위 순회
void PreorderTraverse(BTreeNode node) {
if (node == null) {
return;
}
System.out.println(node.data);
PreorderTraverse(node.leftNode);
PreorderTraverse(node.rightNode);
}
- 후위순회
// 후위 순회
void PostorderTraverse(BTreeNode node) {
if (node == null) {
return;
}
PostorderTraverse(node.leftNode);
PostorderTraverse(node.rightNode);
System.out.println(node.data);
}
순회결과
이진트리를 이용한 수식 표현 (수식트리)
이진트리를 이용한 수식 표현 (수식트리)
부모노드의 자식노드 두 개를 피연산자로 한 후 연산 ex) 7+4*2-1
이진트리를 이용한 수식 구현
중위표기법을 후위표기법으로 변환 중위 표기법을 바로 트리로 구현하기 어려움 (괄호 또는 연산자 우선순위 때문에)
후위표기법을 수식트리로 변환 스택을 이용하여 구현 1) 후위표기법의 앞에서부터 스캔 2) 스캔한 문자가 숫자인 경우 스택에 저장 3) 스캔한 문자가 연산자인 경우 스택에서 두 개를 꺼내 연결한 후 다시 스택에 저장
public BTreeNode createExpTree(String exp){
String postfixExp = PostfixNotation.convPostfix(exp);
Stack<BTreeNode> stack = new Stack<>();
char c = ' ';
for(int i=0; i<postfixExp.length(); i++){
node = createBTreeNode();
c = postfixExp.charAt(i);
// 숫자면
if (Character.isDigit(c)){
setData(node, Character.getNumericValue(c));
}
// 숫자가 아니면 (연산자면) 연결
else {
setData(node, c);
createRightSubTree(node, stack.pop());
createLeftSubTree(node, stack.pop());
}
stack.push(node);
}
return stack.pop();
}
ex) 중위표기법 1+2+3
후위표기법
스택
결과
12+3+
+3+
2 1
3+
3+
+
3
수식트리 계산 - 재귀로 구현 1) 단말노드까지 왼쪽으로 이동 (노드의 좌우가 null일 경우) 후 값 반환 2) 단말노드까지 오른쪽으로 이동 (노드의 좌우가 null일 경우) 후 값 반환 3) 부모노드 값(연산자) 반환 4) 연산자에 맞게 계산 진행 5) 1) ~ 4) 항목 반복
public double calculate(BTreeNode node){
double op1 = 0;
double op2 = 0;
// 단말노드인지 확인
if (getLeftSubTree(node) == null && getRightSubTree(node) == null){
// 단말노드일 경우 해당 노드의 값을 가져와 Double 형식으로 변환
return Double.valueOf(getData(node).toString());
}
// 노드의 왼쪽 피연산자 값 반환
op1 = calculate(getLeftSubTree(node));
// 노드의 오른쪽 피연산자 값 반환
op2 = calculate(getRightSubTree(node));
// 연산자 확인 후 계산
switch (String.valueOf(getData(node))){
case "+":
return op1+op2;
case "-":
return op1-op2;
case "*":
return op1*op2;
case "/":
return op1/op2;
}
return 0;
}
구현
후위표기법으로 변환을 위한 클래스 생성
package Stack;
import Stack.Stack;
import Stack.LinkedList.LinkedListStack;
public class PostfixNotation {
public static String convPostfix(String infix){
char c = ' ';
Stack opStack = new LinkedListStack();
StringBuilder sb = new StringBuilder();
for(int i=0; i<infix.length(); i++){
c = infix.charAt(i);
// 숫자이면 표현
if (Character.isDigit(c)){
sb.append(c);
}
// 연산자 스택이 비어있을 경우 값 push
else if (opStack.isEmpty()){
opStack.push(c);
}
// 숫자가 아니고 연산자 스택이 비어있지 않은 경우 (연산자가 하나라도 스택에 추가된 경우)
else {
// 여는 괄호가 나오면 스택에 저장 후 다음 문자로
if (c == '('){
opStack.push(c);
continue;
}
// 닫는 괄호가 나올 경우
// 스택에 저장된 모든 연산자를 반환
else if (c == ')'){
char check = ' ';
while(true) {
check = (char) opStack.pop();
if (check == '(') {
break;
}
else {
sb.append(check);
}
}
continue;
}
// 현재 연산자의 우선순위가 더 높은 경우
// 스택에 연산자 저장
if (compareOp((char)opStack.peek(), c) > 0){
opStack.push(c);
}
// 현재 연산자의 우선순위가 더 낮거나 같은 경우
// 스택에 있는 우선순위가 높은 연산자를 빼서 표현
else {
while(!opStack.isEmpty()){
if (compareOp((char)opStack.peek(), c) <= 0){
sb.append(opStack.pop());
}
else {
break;
}
}
opStack.push(c);
}
}
}
char check = ' ';
while(!opStack.isEmpty()) {
check = (char) opStack.pop();
if (check != '(') {
sb.append(check);
}
}
return sb.toString();
}
// 연산자 우선순위 반환
public static int getOpPriority(char c){
switch (c) {
case '*':
case '/':
return 3;
case '+':
case '-':
return 2;
case '(':
return 1;
default:
return -1;
}
}
// 연산자 우선순위 비교
public static int compareOp(char stackOp, char curOp){
int stackOpPriority = getOpPriority(stackOp);
int curOpPriority = getOpPriority(curOp);
// 현재 우선순위가 더 높은 경우
if (stackOpPriority < curOpPriority){
return 1;
}
// 우선순위가 같은 경우
else if (stackOpPriority == curOpPriority){
return 0;
}
// 스택의 우선순위가 더 높은 경우
else {
return -1;
}
}
}
수식트리 구현을 위한 클래스 (BinaryTree 상속)
package BinaryTree.LinkedList;
import java.util.Stack;
import Stack.PostfixNotation;
public class ExpressionTree extends BinaryTree {
BTreeNode node;
public BTreeNode createExpTree(String exp){
String postfixExp = PostfixNotation.convPostfix(exp);
Stack<BTreeNode> stack = new Stack<>();
char c = ' ';
for(int i=0; i<postfixExp.length(); i++){
node = createBTreeNode();
c = postfixExp.charAt(i);
// 숫자면
if (Character.isDigit(c)){
setData(node, Character.getNumericValue(c));
}
// 숫자가 아니면 (연산자면) 연결
else {
setData(node, c);
createRightSubTree(node, stack.pop());
createLeftSubTree(node, stack.pop());
}
stack.push(node);
}
return stack.pop();
}
public double calculate(BTreeNode node){
double op1 = 0;
double op2 = 0;
// 단말노드인지 확인
if (getLeftSubTree(node) == null && getRightSubTree(node) == null){
// 단말노드일 경우 해당 노드의 값을 가져와 Double 형식으로 변환
return Double.valueOf(getData(node).toString());
}
// 노드의 왼쪽 피연산자 값 반환
op1 = calculate(getLeftSubTree(node));
// 노드의 오른쪽 피연산자 값 반환
op2 = calculate(getRightSubTree(node));
// 연산자 확인 후 계산
switch (String.valueOf(getData(node))){
case "+":
return op1+op2;
case "-":
return op1-op2;
case "*":
return op1*op2;
case "/":
return op1/op2;
}
return 0;
}
}
수식트리 테스트 구현
package BinaryTree.LinkedList;
public class ExpressionTreeMain {
public static void main(String[] args) {
ExpressionTree expTree = new ExpressionTree();
BTreeNode expNode = expTree.createExpTree("(1+2)*3");
System.out.println(expTree.calculate(expNode));
}
}
먼저 들어간 데이터가 먼저 나오는 구조 (선입선출) (FIFO, First-In, First-Out)
마트에서 계산 대기할 때, 영화관 입장 시 등등
데이터 삽입 시 위치를 알기 위한 Rear 변수 필요 데이터 반환 시 위치를 알기 위한 Front 변수 필요
데이터 삽입과 반환이 이루어지는 위치가 다름 (스택은 동일한 위치에서 pop과 push가 이루어지지만, 큐는 Rear, Front를 통해 위치를 알아내야 함)
추상자료형 (ADT)
자료형
반환값
설명
initialize()
void
큐(Queue) 초기화
isEmpty()
boolean
큐가 비어있는지 확인
enqueue(Data)
void
큐에 데이터 삽입
dequeue()
Data
맨 앞에 있는 데이터 반환 및 삭제
peek()
Data
맨 앞에 있는 데이터 반환 후 삭제하지 않음
배열기반 큐 구현
삽입
삭제
삭제 과정의 문제점 - 아래와 같이 Rear가 배열의 끝까지 이동했지만, 삭제된 공간에는 데이터가 저장되지 않음
- dequeue 시 삭제된 빈 공간을 뒤에 데이터들이 채워줘야하는데, 잦은 데이터의 이동이 발생할 경우 성능에 문제가 생길 수 있어 이를 해결하기 위해 front와 rear의 위치만 변경하도록 해야함
해결방법 - rear와 front가 가리키는 인덱스가 배열의 크기보다 클 경우 front또는 rear값을 0으로 설정하여 배열의 첫번째를 가리킬 수 있도록 함 (원형 큐)
구현 Queue 인터페이스 구현
package Queue;
public interface Queue {
// 큐(Queue) 초기화
void initialize();
// 비어있는지 확인
boolean isEmpty();
// 큐에 데이터 삽입
void enqueue(Object data);
// 큐의 맨 앞에있는 데이터 반환 후 삭제
Object dequeue();
// 큐의 맨 앞에있는 데이터 반환 후 삭제하지 않음
Object peek();
}
Queue 구현
package Queue.Array;
import Queue.Queue;
public class ArrayQueue implements Queue {
private final static int QUEUE_SIZE = 5;
int frontIndex = 0;
int rearIndex = 0;
int countOfData = 0;
Object[] queue = null;
@Override
public void initialize() {
queue = new Object[QUEUE_SIZE];
frontIndex = 0;
rearIndex = 0;
countOfData = 0;
}
@Override
public boolean isEmpty() {
if (countOfData == 0){
return true;
}
return false;
}
@Override
public void enqueue(Object data) {
if (countOfData == QUEUE_SIZE){
System.out.println("더이상 데이터를 추가할 수 없습니다.");
return;
}
// 배열의 끝까지 간 경우 배열의 맨 앞을 가리키도록 rear를 0으로 초기화
if (rearIndex == QUEUE_SIZE){
rearIndex = 0;
}
countOfData++;
queue[rearIndex++] = data;
}
@Override
public Object dequeue() {
if (countOfData == 0){
System.out.println("데이터가 없습니다.");
return null;
}
// 배열의 끝까지 간 경우 배열의 맨 앞을 가리키도록 front를 0으로 초기화
if (frontIndex == QUEUE_SIZE){
frontIndex = 0;
}
countOfData--;
return queue[frontIndex++];
}
@Override
public Object peek() {
if (countOfData == 0){
System.out.println("데이터가 없습니다.");
return null;
}
return queue[frontIndex];
}
}
테스트 구현
package Queue.Array;
import Queue.Queue;
public class ArrayQueueMain {
public static void main(String[] args) {
Queue queue = new ArrayQueue();
queue.initialize();
queue.enqueue(1);queue.enqueue(2);
queue.enqueue(3);queue.enqueue(4);
queue.enqueue(5);
// 데이터 삽입 후 출력
System.out.println("데이터 삽입 후 출력");
while(!queue.isEmpty()){
System.out.println(queue.dequeue());
}
System.out.println("데이터 삭제 후 하나 추가 출력 ");
queue.enqueue(1);queue.enqueue(2);
queue.enqueue(3);queue.enqueue(4);
queue.enqueue(5);
queue.dequeue();
queue.enqueue(6);
while(!queue.isEmpty()){
System.out.println(queue.dequeue());
}
}
}
연결 리스트 기반 큐 구현
배열 기반의 큐와 동일하게 front와 rear 변수 필요
삽입 시 첫 번째 노드와 두 번째 이후의 노드 추가 과정이 다름
삽입
삭제 - front로 큐가 비어있는지 판별할 수 있기 때문에 삭제 시 rear는 신경쓰지 않아도 됨
구현
- 인터페이스는 동일하게 구현
LinkedList 큐 구현
package Queue.LinkedList;
import Queue.Queue;
public class LinkedListQueue implements Queue {
class Node {
Object data;
Node nextNode;
}
Node front = null;
Node rear = null;
int countOfData = 0;
@Override
public void initialize() {
front = null;
rear = null;
countOfData = 0;
}
@Override
public boolean isEmpty() {
if (front == null){
return true;
}
return false;
}
@Override
public void enqueue(Object data) {
Node newNode = new Node();
newNode.data = data;
// 큐가 비어있는 경우 첫 번째 노드 추가
if (isEmpty()){
front = newNode;
rear = newNode;
}
// 두 번째 이후의 노드 추가일 경우 rear의 다음 node 주소를 설정 후 rear값 변경
else {
rear.nextNode = newNode;
rear = newNode;
}
countOfData++;
}
@Override
public Object dequeue() {
if (isEmpty()){
System.out.println("데이터가 없습니다.");
return null;
}
// 제일 앞 쪽 데이터 반환
Object data = front.data;
// front의 다음 노드를 front로 변경
front = front.nextNode;
return data;
}
@Override
public Object peek() {
if (isEmpty()){
System.out.println("데이터가 없습니다.");
return null;
}
return front.data;
}
}
테스트 구현
package Queue.LinkedList;
import Queue.Queue;
public class LinkedListQueueMain {
public static void main(String[] args) {
Queue queue = new LinkedListQueue();
queue.initialize();
queue.enqueue(1);queue.enqueue(2);
queue.enqueue(3);queue.enqueue(4);
queue.enqueue(5);
// 데이터 삽입 후 출력
System.out.println("데이터 삽입 후 출력");
while(!queue.isEmpty()){
System.out.println(queue.dequeue());
}
System.out.println("데이터 삭제 후 하나 추가 출력 ");
queue.enqueue(1);queue.enqueue(2);
queue.enqueue(3);queue.enqueue(4);
queue.enqueue(5);
queue.dequeue();
queue.enqueue(6);
while(!queue.isEmpty()){
System.out.println(queue.dequeue());
}
}
}
위 예시에서 후위 표기법에서 나누기(/) 연산자가 더하기(+) 연산자보다 앞에 있으므로 나누기 연산부터 진행 후 더하기 연산을 한다는 것을 알 수 있음
연산자의 우선순위에 대해 알 필요가 없음 - 연산자의 배치 순서에 따라 연산 순서가 결정됨 - 위 같은 특성 때문에 소괄호에 대한 처리도 불필요함
소괄호가 없는 중위표기법에서 후위 표기법으로 변경하는 방법
예시) 중위표현식 : 5+2/7
숫자는 그대로 표현한다.
연산자는 스택에 저장한다.
스택에 연산자가 있을 경우 우선순위를 비교한다. 3-1. 새로 추가할 연산자의 우선순위가 더 높을 경우 스택에 저장한다. 3-2. 새로 추가할 연산자의 우선순위가 더 낮거나 같을경우 스택에 있는 우선순위가 높은 연산자를 빼서 표현하고, 새로운 연산자는 스택에 저장한다.
위 방법을 반복하며 더 이상 남은 중위 표현식이 없을 경우 스택에 저장된 연산자들을 모두 빼서 표현한다.
중위 표현식
후위 표현식
스택
번호
5+2/7
+2/7
5
방법 1
2/7
5
+
방법 2
/7
52
+
방법 1
7
52
/ +
방법 3-1
527
/ +
방법 1
527/+
방법 4
소괄호가 있는 중위 표현식을 후위 표현식으로 변경하는 방법
( ) 연산자는 우선순위가 다른 연산자들 보다 낮다고 가정 - 어디까지 괄호로 묶여 있는 것인지 판단하기 위해 필요
( 연산자 내부의 수직은 ) 연산자를 만날때까지 기존 후위 표기법과 방식이 동일
) 연산자가 나오면 스택에 저장된 모든 연산자를 표현 - ( ) 연산자는 표현하지 않음
1번부터 반복
예시) 중위 표현식 : (1+2*3)/4
중위 표현식
후위 표현식
스택
(1+2*3)/4
1+2*3)/4
(
+2*3)/4
1
(
2*3)/4
1
+ (
*3)/4
12
+ (
3)/4
12
* + (
)/4
123
* + (
/4
123
) * + (
/4
123*+
4
123*+
/
123*+4
/
123*+4/
소괄호가 있는 중위표기법을 후위 표기법으로 변경하는 기능 구현
기존에 직접 구현한 LinkedListStack을 이용 (java 내부에서 사용하는 Stack 사용해도 무방)
연산자 우선순위를 반환하는 메소드 작성
// 연산자 우선순위 반환
public static int getOpPriority(char c){
switch (c) {
case '*':
case '/':
return 3;
case '+':
case '-':
return 2;
case '(':
return 1;
default:
return -1;
}
}
연산자 우선순위를 비교하는 메소드 작성
// 연산자 우선순위 비교
public static int compareOp(char stackOp, char curOp){
int stackOpPriority = getOpPriority(stackOp);
int curOpPriority = getOpPriority(curOp);
// 현재 우선순위가 더 높은 경우
if (stackOpPriority < curOpPriority){
return 1;
}
// 우선순위가 같은 경우
else if (stackOpPriority == curOpPriority){
return 0;
}
// 스택의 우선순위가 더 높은 경우
else {
return -1;
}
}
후위 표기법으로 변경하는 메소드 작성
public static String convPostfix(String infix){
char c = ' ';
Stack opStack = new LinkedListStack();
StringBuilder sb = new StringBuilder();
for(int i=0; i<infix.length(); i++){
c = infix.charAt(i);
// 숫자이면 표현
if (Character.isDigit(c)){
sb.append(c);
}
// 연산자 스택이 비어있을 경우 값 push
else if (opStack.isEmpty()){
opStack.push(c);
}
// 숫자가 아니고 연산자 스택이 비어있지 않은 경우 (연산자가 하나라도 스택에 추가된 경우)
else {
// 여는 괄호가 나오면 스택에 저장 후 다음 문자로
if (c == '('){
opStack.push(c);
continue;
}
// 닫는 괄호가 나올 경우
// 스택에 저장된 모든 연산자를 반환
else if (c == ')'){
char check = ' ';
while(true) {
check = (char) opStack.pop();
if (check == '(') {
break;
}
else {
sb.append(check);
}
}
continue;
}
// 현재 연산자의 우선순위가 더 높은 경우
// 스택에 연산자 저장
if (compareOp((char)opStack.peek(), c) > 0){
opStack.push(c);
}
// 현재 연산자의 우선순위가 더 낮거나 같은 경우
// 스택에 있는 우선순위가 높은 연산자를 빼서 표현
else {
while(!opStack.isEmpty()){
if (compareOp((char)opStack.peek(), c) <= 0){
sb.append(opStack.pop());
}
else {
break;
}
}
opStack.push(c);
}
}
}
char check = ' ';
while(!opStack.isEmpty()) {
check = (char) opStack.pop();
if (check != '(') {
sb.append(check);
}
}
return sb.toString();
}
후위 표기법 계산
public static double postfixCalculate(String postfix){
Stack stack = new LinkedListStack();
char c = ' ';
double op1 = 0;
double op2 = 0;
for(int i=0; i<postfix.length(); i++){
c = postfix.charAt(i);
// 숫자인 경우 스택에 저장
if (Character.isDigit(c)){
stack.push(c);
}
// 연산자인 경우 계산 후 스택에 저장
else {
op2 = Double.valueOf(stack.pop().toString());
op1 = Double.valueOf(stack.pop().toString());
switch (c){
// op2에 먼저 pop한 이유는 후위 표기법으로 변환할 때 순서가 바뀌기 때문
// ex) 3+2 => 스택에 저장 시 3, 2 순으로 저장되는데 스택은 마지막에 push한
// 데이터가 가장 위에 있으므로
case '+':
stack.push(op1 + op2);
break;
case '-':
stack.push(op1 - op2);
break;
case '*':
stack.push(op1 * op2);
break;
case '/':
stack.push(op1 / op2);
break;
}
}
}
return Double.valueOf(stack.pop().toString());
}
전체 소스코드
package Stack;
import Stack.Stack;
import Stack.LinkedList.LinkedListStack;
public class PostfixNotation {
public static void main(String[] args) {
String infix = "(1+2*3)/4";
String postfix = convPostfix(infix);
System.out.println(postfix);
System.out.println(postfixCalculate(postfix));
}
public static double postfixCalculate(String postfix){
Stack stack = new LinkedListStack();
char c = ' ';
double op1 = 0;
double op2 = 0;
for(int i=0; i<postfix.length(); i++){
c = postfix.charAt(i);
// 숫자인 경우 스택에 저장
if (Character.isDigit(c)){
stack.push(c);
}
// 연산자인 경우 계산 후 스택에 저장
else {
op2 = Double.valueOf(stack.pop().toString());
op1 = Double.valueOf(stack.pop().toString());
switch (c){
// op2에 먼저 pop한 이유는 후위 표기법으로 변환할 때 순서가 바뀌기 때문
// ex) 3+2 => 스택에 저장 시 3, 2 순으로 저장되는데 스택은 마지막에 push한
// 데이터가 가장 위에 있으므로
case '+':
stack.push(op1 + op2);
break;
case '-':
stack.push(op1 - op2);
break;
case '*':
stack.push(op1 * op2);
break;
case '/':
stack.push(op1 / op2);
break;
}
}
}
return Double.valueOf(stack.pop().toString());
}
public static String convPostfix(String infix){
char c = ' ';
Stack opStack = new LinkedListStack();
StringBuilder sb = new StringBuilder();
for(int i=0; i<infix.length(); i++){
c = infix.charAt(i);
// 숫자이면 표현
if (Character.isDigit(c)){
sb.append(c);
}
// 연산자 스택이 비어있을 경우 값 push
else if (opStack.isEmpty()){
opStack.push(c);
}
// 숫자가 아니고 연산자 스택이 비어있지 않은 경우 (연산자가 하나라도 스택에 추가된 경우)
else {
// 여는 괄호가 나오면 스택에 저장 후 다음 문자로
if (c == '('){
opStack.push(c);
continue;
}
// 닫는 괄호가 나올 경우
// 스택에 저장된 모든 연산자를 반환
else if (c == ')'){
char check = ' ';
while(true) {
check = (char) opStack.pop();
if (check == '(') {
break;
}
else {
sb.append(check);
}
}
continue;
}
// 현재 연산자의 우선순위가 더 높은 경우
// 스택에 연산자 저장
if (compareOp((char)opStack.peek(), c) > 0){
opStack.push(c);
}
// 현재 연산자의 우선순위가 더 낮거나 같은 경우
// 스택에 있는 우선순위가 높은 연산자를 빼서 표현
else {
while(!opStack.isEmpty()){
if (compareOp((char)opStack.peek(), c) <= 0){
sb.append(opStack.pop());
}
else {
break;
}
}
opStack.push(c);
}
}
}
char check = ' ';
while(!opStack.isEmpty()) {
check = (char) opStack.pop();
if (check != '(') {
sb.append(check);
}
}
return sb.toString();
}
// 연산자 우선순위 반환
public static int getOpPriority(char c){
switch (c) {
case '*':
case '/':
return 3;
case '+':
case '-':
return 2;
case '(':
return 1;
default:
return -1;
}
}
// 연산자 우선순위 비교
public static int compareOp(char stackOp, char curOp){
int stackOpPriority = getOpPriority(stackOp);
int curOpPriority = getOpPriority(curOp);
// 현재 우선순위가 더 높은 경우
if (stackOpPriority < curOpPriority){
return 1;
}
// 우선순위가 같은 경우
else if (stackOpPriority == curOpPriority){
return 0;
}
// 스택의 우선순위가 더 높은 경우
else {
return -1;
}
}
}
결과 전위 표기법 : (1+2*3)/4
전위 표기법 : ((4+2)/4)-(3+2/(7*5))
2자리 이상의 숫자를 연산하려면 List와 StringBuilder로 구현 가능 StringBuilder를 이용해 문자가 나올 때까지 반복하고, 연산자가 나올 경우 숫자를 리스트에 저장하는 방식으로 구현 가능
기본 연결 리스트에서 이전 노드를 가리키는 prev 변수 필요 - 기존에 구현한 연결 리스트에서는 삭제할 노드의 이전 노드와 삭제할 노드의 다음 노드를 사로 연결해주기 위해 앞에서부터 탐색하여 이전 노드를 찾음 (첫번째부터 탐색을 진행하기 때문에 데이터가 많아질수록 부하가 발생) - 양방향 연결 리스트의 경우 이전 노드를 바로 알 수 있기 때문에 성능상 이점이 있음
추상 자료형
자료형
반환값
내용
initialize()
void
리스트 초기화
insert(Data)
boolean
리스트에 데이터 삽입
first()
Data
첫번째 데이터를 가리키도록 함 (Dummy 노드를 추가한 경우 반환값을 받을 필요 없으나, 기본 연결 리스트 구현 시에는 필요하기 때문에 반환값을 Data로 주었음)
next()
Data
현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 해당 값을 반환
remove()
Data
현재 참조하고 있는 데이터를 삭제
count()
int
리스트에 있는 데이터의 총 개수
리스트 초기화 - 헤드가 더미를 가리키게 함
public void initialize() {
head = new Node();
cur = head;
countOfData = 0;
}
데이터 추가 - 2와 4를 추가했을 때의 상태
public boolean insert(Object data) {
try {
Node newNode = new Node();
newNode.data = data;
// 헤드의 nextNode가 null이 아닐 경우
// 즉, 데이터가 하나라도 추가된 경우를 뜻함
if (head.nextNode != null) {
head.nextNode.prevNode = newNode;
}
// 새로운 노드의 다음 노드는 기존에 head가 가리키던 nextNode를 받음
newNode.nextNode = head.nextNode;
// 새로운 노드의 이전 노드는 머리를 가리켜야 함
newNode.prevNode = head;
// 헤드의 다음 노드는 새로운 노드를 가리킴
head.nextNode = newNode;
countOfData++;
return true;
}catch (Exception ex){
System.out.println(ex.getMessage());
return false;
}
}
데이터 삭제 - 4를 삭제했을 경우 - 삭제할 노드의 이전 노드의 다음 노드가 가리키는 값을 삭제할 노드의 다음 노드 값으로 변경 - 삭제할 노드의 다음 노드의 이전 노드가 가리키는 값을 삭제할 노드의 이전 노드 값으로 변경
public Object remove() {
if (countOfData == 0){
System.out.println("삭제할 노드가 없습니다.");
return null;
}
Node rNode = cur;
// 현재 노드의 이전 노드가 가리키는 다음 노드를 현재 노드의 다음 노드로 변경
cur.prevNode.nextNode = cur.nextNode;
if (cur.nextNode != null) {
cur.nextNode.prevNode = cur.prevNode;
}
countOfData--;
return rNode;
}
데이터 조회 - first 호출 시 - next 호출 시
구현
디렉토리 구조
인터페이스 구현 - 기존 순차 리스트 인터페이스와 동일
package List;
// 다형성을 위해 List를 인터페이스로 생성
public interface List {
// 리스트 초기화
void initialize();
// 리스트에 데이터 삽입 (어떤 값이 올 지 모르므로 Object를 인자로 받음)
boolean insert(Object data);
// 첫 번째 데이터를 가리키도록 하며 값을 반환
Object first();
// 현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
Object next();
// 현재 참조하고 있는 데이터를 지움
Object remove();
// 리스트에 저장된 데이터의 개수를 반환
int count();
}
양방향 연결 리스트 구현
package List.LinkedList.Double;
import List.List;
public class DoublyLinkedList implements List {
public class Node {
public Object data;
public Node prevNode;
public Node nextNode;
}
Node head = null;
Node cur = null;
int countOfData = 0;
@Override
public void initialize() {
head = new Node();
cur = head;
countOfData = 0;
}
@Override
public boolean insert(Object data) {
try {
Node newNode = new Node();
newNode.data = data;
// 헤드의 nextNode가 null이 아닐 경우
// 즉, 데이터가 하나라도 추가된 경우를 뜻함
if (head.nextNode != null) {
head.nextNode.prevNode = newNode;
}
// 새로운 노드의 다음 노드는 기존에 head가 가리키던 nextNode를 받음
newNode.nextNode = head.nextNode;
// 새로운 노드의 이전 노드는 머리를 가리켜야 함
newNode.prevNode = head;
// 헤드의 다음 노드는 새로운 노드를 가리킴
head.nextNode = newNode;
countOfData++;
return true;
}catch (Exception ex){
System.out.println(ex.getMessage());
return false;
}
}
@Override
public Object first() {
// 현재 위치를 가지고 있는 cur 변수를 head로 설정 (맨 처음 위치로)
cur = head;
return cur;
}
@Override
public Object next() {
// 현재 가리키고 있는 노드의 다음 노드가 null인 경우 마지막 노드로 판단
if (cur.nextNode == null){
System.out.println("마지막 노드입니다.");
return null;
}
// 현재 가리키고 있는 노드의 다음 노드로 설정
cur = cur.nextNode;
return cur.data;
}
@Override
public Object remove() {
if (countOfData == 0){
System.out.println("삭제할 노드가 없습니다.");
return null;
}
Node rNode = cur;
// 현재 노드의 이전 노드가 가리키는 다음 노드를 현재 노드의 다음 노드로 변경
cur.prevNode.nextNode = cur.nextNode;
if (cur.nextNode != null) {
cur.nextNode.prevNode = cur.prevNode;
}
countOfData--;
return rNode;
}
@Override
public int count() {
return countOfData;
}
}
메인 구현 - 데이터 추가/삭제/조회 기능 테스트
package List.LinkedList.Double;
public class DoublyLinkedListMain {
public static void main(String[] args) {
DoublyLinkedList linkedList = new DoublyLinkedList();
// 리스트 초기화
linkedList.initialize();
// 리스트에 데이터 삽입
linkedList.insert(1); linkedList.insert(2);
linkedList.insert(3); linkedList.insert(4);
linkedList.insert(5); linkedList.insert(6);
// 첫번째 노드로 설정
Object data = null;
linkedList.first();
// data가 null이 될 때까지 반복
while((data = linkedList.next()) != null) {
System.out.println(data);
}
// 데이터 삭제
Object remove = null;
linkedList.first();
while((data = linkedList.next()) != null){
if ((int)data == 1){
remove = linkedList.remove();
System.out.println((int)data + "가 삭제되었습니다.");
remove = null;
}
}
// 첫번째 노드로 설정
linkedList.first();
// data가 null이 될 때까지 반복
while((data = linkedList.next()) != null) {
System.out.println(data);
}
}
}
데이터들을 Node로 관리 (Node : data, 다음 노드의 주소값으로 이루어져 있음)
리스트는 데이터의 저장 순서를 유지해야하는 자료구조가 아님
Node
리스트의 구성
필요한 Node들 head : 리스트의 머리를 가리킴 tail : 리스트의 꼬리를 가리킴 cur : 데이터의 조회에 사용됨
head에 데이터 추가 시 장점 : tail 노드가 불필요 단점 : 저장 순서가 유지되지 않음
tail에 데이터 추가 시 장점 : 저장 순서가 유지됨 단점 : tail 노드가 필요
데이터 추가 tail 또는 head쪽에 데이터 추가 후 tail 또는 head가 가리키는 값 변경 ex) tail에 데이터 추가 시
데이터 조회 cur Node를 이용해 조회 ex) data2 조회
데이터 삭제 삭제할 노드를 가리키고 있는 노드의 next 값을 삭제할 노드가 가진 next 값으로 변경
추상 자료형 (ADT)
자료형
반환값
내용
initialize()
void
리스트 초기화
insert(Node)
boolean
리스트에 데이터 저장
next()
Node
현재 가리키고 있는 노드의 다음 노드
remove()
Node
현재 가리키고 있는 노드를 삭제
count()
int
현재 리스트에 있는 데이터의 개수
구현
디렉토리 구조
인터페이스 구현 다형성을 위해 List관련 메소드를 인터페이스로 구현
package List;
// 다형성을 위해 List를 인터페이스로 생성
public interface List {
// 리스트 초기화
void initialize();
// 리스트에 데이터 삽입 (어떤 값이 올 지 모르므로 Object를 인자로 받음)
boolean insert(Object data);
// 첫 번째 데이터를 가리키도록 하며 값을 반환
Object first();
// 현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
Object next();
// 현재 참조하고 있는 데이터를 지움
Object remove();
// 리스트에 저장된 데이터의 개수를 반환
int count();
}
단일 연결 리스트 구현 실제 단일 연결 리스트 구현
package List.LinkedList.Single;
import List.List;
public class SingleLinkedList implements List {
public class Node {
Object data;
Node nextNode;
public Node(Object data, Node nextNode){
this.data = data;
this.nextNode = nextNode;
}
public Node() {
this.data = null;
this.nextNode = null;
}
}
Node head = null;
Node tail = null;
Node cur = null;
Node newNode = null;
int dataCount = 0;
@Override
public void initialize() {
head = null;
tail = null;
cur = null;
newNode = null;
}
@Override
public boolean insert(Object data) {
try {
newNode = new Node(data, null);
if (head == null) {
head = newNode;
} else {
tail.nextNode = newNode;
}
tail = newNode;
dataCount++;
return true;
}catch (Exception ex){
return false;
}
}
@Override
public Object first() {
try {
if (head == null) {
return null;
}
cur = head;
return cur.data;
}catch (Exception ex){
return null;
}
}
@Override
public Object next() {
try{
if (head == null){
return null;
}
if (cur.nextNode == null){
System.out.println("마지막 노드입니다.");
return null;
}
cur = cur.nextNode;
return cur.data;
}catch (Exception ex) {
return null;
}
}
@Override
public Object remove() {
try{
if (head == null){
return null;
}
Node tmpNode = head;
while(tmpNode.nextNode != cur){
tmpNode = tmpNode.nextNode;
}
tmpNode.nextNode = cur.nextNode;
dataCount--;
return cur;
}catch (Exception ex){
return null;
}
}
@Override
public int count() {
return dataCount;
}
}
메인 구현 데이터 삽입, 삭제 및 조회 기능 테스트
package List.LinkedList.Single;
public class SingleLinkedListMain {
public static void main(String[] args) {
SingleLinkedList linkedList = new SingleLinkedList();
// 리스트 초기화
linkedList.initialize();
// 리스트에 데이터 삽입
linkedList.insert(1); linkedList.insert(2);
linkedList.insert(3); linkedList.insert(4);
linkedList.insert(5); linkedList.insert(6);
// 첫번째 노드로 설정 및 데이터 가져오기
Object data = linkedList.first();
System.out.println(data);
// data가 null이 될 때까지 반복
while((data = linkedList.next()) != null) {
System.out.println(data);
}
// 데이터 삭제
Object remove = null;
data = linkedList.first();
if ((int)data == 4){
remove = linkedList.remove();
System.out.println((int)data + "가 삭제되었습니다.");
remove = null;
}
while((data = linkedList.next()) != null){
if ((int)data == 4){
remove = linkedList.remove();
System.out.println((int)data + "가 삭제되었습니다.");
remove = null;
}
}
// 첫번째 노드로 설정 및 데이터 가져오기
data = linkedList.first();
System.out.println(data);
// data가 null이 될 때까지 반복
while((data = linkedList.next()) != null) {
System.out.println(data);
}
}
}
더미노드를 이용한 단순 연결 리스트
기존 연결 리스트에서는 head가 첫 번째 노드를 가리키고 있음 Dummy Node 이용 시 head가 더미 노드를 가리키고 있음
노드들을 추가/삭제 및 조회 시 첫 번째 노드와 두 번째 이후의 노드간 차이가 있음 - 첫번째 노드를 먼저 가져와서 처리한 후 next 메소드로 다음 노드를 참조하는 방식
단점 1) 배열의 길이가 사전에 정의되어야 함 2) 중간 데이터 삭제 시 해당 인덱스 이후의 값들은 한 칸씩 이동이 발생
설명
삽입 - 보통 배열의 마지막에 데이터가 삽입되며, 삽입 시 배열의 크기도 고려해야 함 - 배열의 중간에 데이터를 삽입하기 위해서는 배열의 길이가 충분한지 확인해야 하며, 삽입된 위치 뒤에 존재하는 모든 데이터들이 한 칸씩 뒤로 이동해야 하므로 중간에 데이터 삽입 시 비효율적 - 시간 복잡도 : O(n)
삭제 - 배열의 중간에 위치한 데이터를 삭제할 경우 해당 위치의 뒤 데이터들은 한 칸씩 앞으로 이동해야 하므로 배열의 크기가 크고 삭제가 빈번할수록 비효율적 - 시간복잡도 : O(n)
조회(검색) - 배열에 존재하는 데이터에 대한 인덱스 값들이 고정되어 있기 때문에 조회가 간편함 - 시간복잡도 : O(n) [찾으려는 값이 없을 경우]
접근 - 배열의 인덱스로 데이터에 바로 접근할 수 있음 - 시간복잡도 : O(1)
추상 자료형 (ADT)
자료형
반환값
내용
initialize()
void
리스트 초기화
insert(Object data)
boolean
리스트에 데이터 저장
first()
Object
첫 번째 데이터를 가리키도록 하며 값을 반환
next()
Object
현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
remove()
Object
현재 참조하고 있는 데이터를 지움
count()
int
리스트에 저장된 데이터의 개수를 반환
구현
디렉토리 구조
인터페이스 구현 다형성을 위해 List관련 메소드를 인터페이스로 구현
package List;
// 다형성을 위해 List를 인터페이스로 생성
public interface List {
// 리스트 초기화
void initialize();
// 리스트에 데이터 삽입 (어떤 값이 올 지 모르므로 Object를 인자로 받음)
boolean insert(Object data);
// 첫 번째 데이터를 가리키도록 하며 값을 반환
Object first();
// 현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
Object next();
// 현재 참조하고 있는 데이터를 지움
Object remove();
// 리스트에 저장된 데이터의 개수를 반환
int count();
}
순차 리스트 구현 실제 리스트 코드 작성
package List.ArrayList;
import List.List;
public class ArrayList implements List {
// 리스트 최대 개수를 10으로 지정
final int MAX_LIST_COUNT = 10;
Object[] list = new Object[MAX_LIST_COUNT];
// 현재 위치 저장 변수 (아무것도 참조하고 있지 않으므로 -1)
int curPosition = -1;
// 리스트에 저장된 데이터 개수
int countOfData = 0;
@Override
public void initialize() {
curPosition = -1;
countOfData = 0;
for(int i=0; i<MAX_LIST_COUNT; i++){
list[i] = null;
}
}
@Override
public boolean insert(Object data) {
if (data == null){
System.out.println("null 값을 추가할 수 없습니다.");
return false;
}
if (countOfData >= 100){
System.out.println("더이상 데이터를 추가할 수 없습니다.");
return false;
}
// 리스트에 데이터 저장
list[countOfData++] = data;
return true;
}
@Override
public Object first() {
if (countOfData == 0){
System.out.println("데이터가 없습니다.");
return null;
}
// 첫 번째를 가리키도록 설정
curPosition = 0;
// 첫 번째 데이터 반환
return list[curPosition];
}
@Override
public Object next() {
if (curPosition >= countOfData - 1){
System.out.println("데이터가 없습니다.");
return null;
}
curPosition++;
return list[curPosition];
}
@Override
public Object remove() {
if (countOfData == 0){
System.out.println("데이터가 없습니다.");
return null;
}
// 현재 참조된 데이터를 제거하기 위해 변수에 할당
Object rData = list[curPosition];
// 한 칸씩 당기기 위한 반복문
for(int i=curPosition; i<countOfData - 1; i++){
list[i] = list[i+1];
}
// 데이터가 제거됐으므로 개수와 위치를 하나씩 감소
countOfData--;
curPosition--;
return rData;
}
@Override
public int count() {
return countOfData;
}
}
메인 구현 데이터 삽입, 삭제 및 조회 기능 테스트
package List.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList list = new ArrayList();
// 리스트 초기화
list.initialize();
// 리스트 데이터 추가
list.insert(1); list.insert(2);
list.insert(3); list.insert(4);
list.insert(5); list.insert(6);
// 첫 번째 인덱스를 가리키도록 설정
Object data = list.first();
System.out.println(data);
// data가 null이 아닐때까지 반복
while((data = list.next()) != null){
System.out.println(data);
}
// data 삭제
Object rData = null;
data = list.first();
if ((int)data == 4){
rData = list.remove();
System.out.println(rData + " 데이터가 삭제되었습니다.");
rData = null;
}
while((data = list.next()) != null){
if ((int)data == 4){
rData = list.remove();
System.out.println(rData + " 데이터가 삭제되었습니다.");
rData = null;
}
}
// 삭제 후 재출력
data = list.first();
System.out.println(data);
// data가 null이 아닐때까지 반복
while((data = list.next()) != null){
System.out.println(data);
}
}
}
