[자바][자료구조] DoublyLinked List 이중연결 리스트 삽입 삭제 탐색

1. 목적 

원형 이중 연결 리스트(DoublyLinkedList) 의 삽입, 삭제, 탐색을 구현합니다.

코드가 있고 따로 파일을 저장해 놨으니 필요하시다면 다운받아서 사용하세요^^

 

2. 코드의 동작 설명

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();

사이즈를 반환합니다.

 

 

 

3. 코드

 

package hahaha;

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();

}

//DLList

package hahaha;



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 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();

}

}







//main

package hahaha;

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, size, p, or q");

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("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("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("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"))

print(list);

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

System.out.println("Front of the list: "+list.peekFirst());

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

System.out.println("Rear of the list: "+list.peekLast());

System.out.print("> ");

command = input.next();

}

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

input.close();

}



private static void print(DLList<Integer> list) {

list.print();

}

}

코드.txt

0.00MB