[자바][자료구조] 이중연결자 Iterator

1.개요

원형 이중 연결 리스트에 반복자를 구현하여 다음의 문제를 해결합니다.

  

 

2.동작

DLList 코드 동작

public void addFirst(T item)

size가 0이라면 head에 바로 추가합니다. 아니라면 새로운 노드와 last node를 연결하고, 새로운 노드와 first node를 연결합니다. last node의 next를 새로운 노드에 연결하고, first node의 prev를 새로운 노드로 설정합니다. 새로운 노드가 시작점이 됩니다.

public void addLast(T item)

size가 0이라면 head에 바로 추가합니다. 아니라면 새로운 노드와 last node를 연결하고, 새로운 노드와 first node를 연결합니다. last node의 next를 새로운 노드에 연결하고, first node의 prev를 새로운 노드로 설정합니다.

public T removeFirst()

size가 0일 경우 예외처리를 실시합니다. 임시 값에 지울값을 저장하고, 지울 노드에서 이전 노드의 next를 지울노드의 다음노드로 설정하고, 지울 노드에서 다음 노드의 prev를 지울 노드의 이전 노드로 설정합니다. 이제부턴 head의 다음 노드가 시작점이 됩니다.

public T removeLast()

size가 0일 경우 예외처리를 실시합니다. 임시 값에 지울값을 저장하고, 지울 노드에서 이전 노드의 next를 지울노드의 다음노드로 설정하고, 지울 노드에서 다음 노드의 prev를 지울 노드의 이전 노드로 설정합니다.

public T search(T item)

노드의 끝까지 next로 나아가면서 값을 비교하고, 순환을 완료하면 종료합니다.

public T remove(T item)

노드의 끝까지 next로 나아가면서 값을 비교합니다. 임시 값에 지울값을 저장하고, 지울 노드에서 이전 노드의 next를 지울노드의 다음노드로 설정하고, 지울 노드에서 다음 노드의 prev를 지울 노드의 이전 노드로 설정합니다. 만약 지우는 값이 head라면 head를 변경합니다.

public T peekFirst();

맨 앞 노드를 반환합니다.

public T peekLast();

맨 뒤 노드를 반환합니다.

public boolean isEmpty();

비었는지 여부를 확인합니다.

public int size();

사이즈를 반환합니다.

public Iterator iterator()

Iterator를 overriding합니다.

public Node getNodeAt(int index)

index 값에 해당하는 노드의 next를 노드에 저장합니다.

public void clone(DLList dlist)

iterator의 값이 기존 list에 영향을 주지 않기위한 clone입니다.

 

DLListIterator코드의 동작

public boolean hasNext()

size가 0일 때는 false size가 0이 아닌경우에는 true를 반환합니다.

public Object next()

Next값이 있다면 current Node의 next값을 호출, 반환은 그 이전의 node값을 반환합니다.

public Object remove()

current node의 값을 temp에 저장한후 current next로 이동하고 이전 노드를 삭제합니다.

 

main코드의 동작

private static <T> DLList<Integer> removeDup(DLList<Integer> list)

Iterator를 이용해서 하나씩 받아와 next가 없으면 종료하는 while문을 이용합니다. 새로운 결과 값에 겹치지 않는 값만 저장합니다.

private static <T> T josephusProblem(DLList<Integer> list, int k)

Iterator를 이용해서 하나씩 받아와 next가 없으면 종료하는while문을 이용합니다. k-1만큼 이동한 후에 삭제해줍니다.

private static <T> void printList(DLList<Integer> list)

리스트에서 하나씩 제거하면서 return 받아 출력합니다.

 

 

 

3.코드

//interface Iteraor<T>

public interface Iteraor<T> {

 

public boolean hasNext();

 

public T next();

 

public Object remove();

}

 

//class DLListIterator

class DLListIterator implements Iteraor {

private DLList dlist = new DLList();

Node curnode ;

 

public DLListIterator(DLList dlist) {

this.dlist.clone(dlist);

if(dlist.isEmpty()) this.curnode = null;

else this.curnode = this.dlist.getNodeAt(0);

}

 

public boolean hasNext() {

if (dlist.size()!=0) {

return true;

} else {

return false;

}

}

 

 

public Object next() {

Node tempNode = null;

if (hasNext()) {

tempNode = curnode;

curnode = curnode.next;

}

return tempNode;

}

 

@Override

public Object remove() {

Object temp = null;

if (hasNext()) {

Node tempNode = curnode;

curnode = curnode.next;

temp = tempNode.item;

dlist.remove(tempNode);

}

return temp;

}

}

 

//class DLList<T>

interface DoublyLinkedList<T> {

public void addFirst(T item);

 

public void addLast(T item);

 

public T removeFirst();

 

public T removeLast();

 

public T search(T item);

 

public T remove(T item);

 

public T peekFirst();

 

public T peekLast();

 

public boolean isEmpty();

 

public int size();

 

public abstract Iteraor iterator();

}

 

 

class Node<T> {

public T item;

public Node<T> next;

public Node<T> prev;

 

public Node() {

next = null;

prev = null;

}

 

public Node(T item) {

this.item = item;

next = null;

prev = null;

}

}

 

class DLList<T> implements DoublyLinkedList<T> {

private Node<T> head;

private int size = 0;

 

public void addFirst(T item) {

Node newNode = new Node(item);

if (size == 0) {

head = newNode;

head.prev = head;

head.next = head;

} else {

newNode.prev = head.prev;

newNode.next = head;

head.prev.next = newNode;

head.prev = newNode;

head = newNode;

}

size++;

}

 

public void addLast(T item) {

Node newNode = new Node(item);

if (size == 0) {

head = newNode;

head.prev = head;

head.next = head;

} else {

newNode.prev = head.prev;

newNode.next = head;

head.prev.next = newNode;

head.prev = newNode;

}

size++;

}

 

 

 

public boolean isEmpty() {

return size == 0;

}

 

public T removeFirst() {

if (size == 0)

throw new java.util.NoSuchElementException("remove(): list empty");

T temp = head.item;

head.prev.next = head.next;

head.next.prev = head.prev;

head = head.next;

size--;

if (size == 0)

head = null;

return temp;

}

 

public T removeLast() {

if (size == 0)

throw new java.util.NoSuchElementException("remove(): list empty");

T temp = head.prev.item;

head.prev.prev.next = head;

head.prev = head.prev.prev;

size--;

if (size == 0)

head = null;

return temp;

}

 

public T search(T item) {

Node cur = head;

while (cur != null) {

if (cur.item == item) {

return (T) cur.item;

}

cur = cur.next;

if (cur == head)

break;

}

return null;

}

 

public T remove(T item) {

Node cur = head;

while (cur != null) {

if (cur.item == item) {

T temp = (T) cur.item;

cur.prev.next = cur.next;

cur.next.prev = cur.prev;

if (cur == head)

head = head.next;

cur = null;

size--;

if (size == 0)

head = null;

return temp;

}

cur = cur.next;

if (cur == head)

break;

}

return null;

}

 

public void remove(Node node) {

Node cur = head;

while (cur != null) {

if (cur == node) {

cur.prev.next = cur.next;

cur.next.prev = cur.prev;

if (cur == head)

head = head.next;

cur = null;

size--;

if (size == 0)

head = null;

return;

}

cur = cur.next;

if (cur == head)

break;

}

}

 

public T peekFirst() {

if (size == 0)

throw new java.util.NoSuchElementException("peek(): list empty");

return head.item;

}

 

public T peekLast() {

if (size == 0)

throw new java.util.NoSuchElementException("peek(): list empty");

return head.prev.item;

}

 

public int size() {

return size;

}

 

public void print() {

Node cur = head;

while (cur != null) {

System.out.print(cur.item + " ");

cur = cur.next;

if (cur == head)

break;

}

System.out.println();

}

 

@Override

public Iteraor iterator() {

return new DLListIterator(this);

}

 

public Node getNodeAt(int index) {

Node cur = head;

int i = 0;

while (cur != null) {

if(i == index) break;

cur = cur.next;

i++;

if (cur == head)

break;

}

return cur;

}

 

public void clone(DLList dlist) {

Node cur;

cur = dlist.head;

this.size = 0;

this.head = null;

int i = 0;

while (cur != null) {

this.addLast((T) cur.item);

cur = cur.next;

i++;

if (cur == dlist.head)

break;

}

}

}

 

//main

import java.io.FileNotFoundException;

import java.util.Scanner;

 

public class main {

 

public static void main(String[] args) throws FileNotFoundException {

System.out.println("Enter a command: af, al, rf, rl, r, s, pf, pl, p(rint), size, for, d(remove duplicates), j(josephus), or q(uit)");

System.out.print("> ");

 

Scanner input = new Scanner(System.in);

String command = input.next();

 

DLList<Integer> list = new DLList<Integer>();

int item;

 

while (!command.equals("q")) {

if (command.equals("af")) {

item = input.nextInt();

list.addFirst(item);

} else if (command.equals("al")) {

item = input.nextInt();

list.addLast(item);

} else if (command.equals("r")) {

item = input.nextInt();

if (list.remove(item) != null)

System.out.println(item + " removed.");

else

System.out.println("No such " + item + "!");

} else if (command.equals("s")) {

item = input.nextInt();

if (list.search(item) != null)

System.out.println(item + " found.");

else

System.out.println("No such " + item + "!");

} else if (command.equals("rf"))

list.removeFirst();

else if (command.equals("rl"))

list.removeLast();

else if (command.equals("size"))

System.out.println("size: " + list.size());

else if (command.equals("p"))

printList(list);

else if (command.equals("for")) {

Iteraor itr = list.iterator();

for (int i;itr.hasNext();) {

i = (int) itr.remove();

System.out.print(i + " ");

}

System.out.println();

} else if (command.equals("d")) {

list = removeDup(list);

printList(list);

} else if (command.equals("j")) {

System.out.print("Enter kth number to be out : ");

int k = input.nextInt();

int aliveNum = josephusProblem(list, k);

System.out.println(aliveNum + " is alive.");

}

System.out.print("> ");

command = input.next();

}

System.out.println("Commands Terminated.");

input.close();

}

 

private static <T> DLList<Integer> removeDup(DLList<Integer> list) {

Iteraor itr = list.iterator();

DLList<Integer> result = new DLList<>();

while(itr.hasNext()){

int temp = (int) itr.remove();

if(result.search(temp)==null){

result.addLast(temp);

}

}

return result;

}

 

private static <T> T josephusProblem(DLList<Integer> list, int k) {

Iteraor itr = list.iterator();

Node cur = null;

int min;

while(itr.hasNext()){

for(int i = 0; i< k-1;i++){

cur = (Node) itr.next();

}

itr.remove();

}

DLList <Integer> newlist = new DLList<Integer>();

newlist.addFirst((Integer) cur.item);

list.clone(newlist);

return (T) cur.item;

}

 

private static <T> void printList(DLList<Integer> list) {

Iteraor itr = list.iterator();

while(itr.hasNext()){

System.out.print(itr.remove()+" ");

}

System.out.println();

}

 

}

 

 

 

 

 

 

 

 

4.출력결과

Enter a command: af, al, rf, rl, r, s, pf, pl, p(rint), size, for, d(remove duplicates), j(josephus), or q(uit)

> af 4

> af 2

> af 9

> al 7

> al 3

> al 8

> p

9 2 4 7 3 8

> j

Enter kth number to be out : 3

9 is alive.

> p

9

> af 2

> al 4

> p

2 9 4

> af 2

> af 4

> af 4

> al 2

> al 2

> p

4 4 2 2 9 4 2 2

> d

4 2 9

> for

4 2 9

> af 7

> af 6

> af 1

> af 3

> p

3 1 6 7 4 2 9

> j

Enter kth number to be out : 2

9 is alive.

> p

9

> af 9

> af 9

> af 9

> af 9

> p

9 9 9 9 9

> d

9

> p

9

> q

Commands Terminated.