Data Structure and Algorithm/이론

DoublyLinkedList 코드

Razelo 2020. 12. 17. 22:19
package list.doublylinkedlist.implementation;
//양방향성이 있는 이중연결시스트. 더 많은 메모리를 사용하는 것이 단점임. 
public class DoublyLinkedList {
	private Node head;
	private Node tail; 
	private int size = 0;
	
	private class Node{
		private Object data;
		private Node next;
		private Node prev;
		
		public Node(Object input) {
			this.data = input;
			this.next = null;
			this.prev = null;
		}
		public String toString() {
			return String.valueOf(this.data);
		}
	}
	public void addFirst(Object input) {
		Node newNode = new Node(input);
		newNode.next = head; //addFirst 한번 더 호출했을때.. 왜냐면 head는 원래 첫 노드를 가리키니까... 
		
		if(head != null) 
			head.prev = newNode;
		
		head = newNode;
		size++;
		if(head.next == null) {
			tail = head;
		}
	}
	public void addLast(Object input) {
		Node newNode = new Node(input);
		if(size == 0) {
			addFirst(input);
		}else { //데이터가 하나 이상인경우에만 사용해야하기 때문에, 
			tail.next = newNode;
			newNode.prev = tail; //뒤랑 이어준다. 
			tail = newNode;
			size++;
		}
	}
	Node node(int index) { //상당히 유용한 메소드이다. 외부로 노출되면 안된다. 
		if(index<size/2) {
			Node x = head;
			for(int i = 0;i<index;i++) {
				x = x.next;	
			}
			return x;
		}
		else {
			Node x = tail;
			for(int i = size-1;i>index;i--) {
				x = x.prev;
			}
			return x;
		}
	}
	public void add(int k,Object input) { //k는 인덱스다. 
		if(k == 0) {
			addFirst(input);
		}else {
			Node temp1 = node(k-1);   //이전 노드 
			Node temp2 =  temp1.next;
			Node newNode = new Node(input);
			temp1.next = newNode;
			newNode.next = temp2;
			if(temp2 != null) {
				temp2.prev = newNode;
			}
			newNode.prev = temp1;
			size++;
			if(newNode.next == null) {
				tail = newNode;
			}
		}
	}
	
	public String toString() {
		if(head == null) {
			return "[]";
		}
		else {
			Node temp = head;
			String str = "[";
			while(temp.next != null) { 
				str += temp.data+", ";
				temp = temp.next;
			}
			str+=temp.data; //마지막 노드때문에 마지막은 temp.next가 null이니까. 
			return str+"]";
		}
	}
	public Object removeFirst() {
		Node temp = head;
		head = head.next;
		Object returnData = temp.data;
		temp = null;
		if(head != null) {
			head.prev = null;
		}
		size--;
		return returnData;
	}
	public Object remove(int k) {
		if(k == 0) {
			return removeFirst();
		}
		Node temp = node(k-1); //이전 노드 조회 
		Node todoDeleted  = temp.next;
		temp.next = temp.next.next;
		if(temp.next != null) {
			temp.next.prev = temp;		
		}
		Object returnData = todoDeleted.data;
		if(todoDeleted == tail) {
			tail = temp;
		}
		todoDeleted = null;
		size--;
		return returnData;
	}
	public Object removeLast() {
		return remove(size-1);
	}
	public int size() {
		return size;
	}
	public Object get(int k) {
		Node temp = node(k);
		return temp.data;
	}
	public int indexOf(Object data) {
		Node temp = head;
		int index = 0;
		while(temp.data != data) {
			temp = temp.next;
			index++;
			if(temp == null) { //가장 끝 노드 노달함 
				return -1;
			}
		}
		return index;
	}
	
	public ListIterator listIterator() {
		return new ListIterator();
	}
	public class ListIterator{  
		private Node next;
		private Node lastReturned; //항상 next의 전을 가리킨다고 보면됨. 근데 아닌 경우도 있음... (remove때였나? )
		private int nextIndex = 0;
		ListIterator(){
			next = head;
		}
		public Object next() {
			lastReturned = next;
			next = next.next;
			nextIndex++;
			return lastReturned.data;
		}
		public Object previous() {
			if(next == null) {
				lastReturned = next = tail;
			}else {
				lastReturned = next = next.prev;
			}
			nextIndex--;
			return lastReturned.data;
		}
		public boolean hasPrevious() {
			return nextIndex>0;
		}
		public boolean hasNext() {
			return nextIndex<size();
		}
		public void add(Object input) {
			Node newNode = new Node(input);
			if(lastReturned == null) { // 첫번째 위치에 추가하는 작업 
				head = newNode;
				newNode.next = next;	
			}else {                    //중간에 끼워넣는 작업
				lastReturned.next = newNode;
				newNode.prev = lastReturned;
				if(next != null) {
					newNode.next = next;
					next.prev = newNode;
				}else {
					tail = newNode;
				}
			}
			lastReturned = newNode; //lastReturned는 항상 next의 뒤에 따라온다. 
			nextIndex++;
			size++;
		}
		public void remove() {//p 이전노드, n 다음 노드 /첫번쨰/ 중간/ 끝을 삭제하는 내용이 들어있다. 
			if(nextIndex == 0) { //lastReturned == null 로 해도 같음. 
				throw new IllegalStateException();
			}
			Node n = lastReturned.next;
			Node p = lastReturned.prev;
			if(p == null) {
				head = n;
				head.prev = null;
				lastReturned = null;
			}else { //삭제하려고 하는 노드의 이전 노드가 존재한다면, 
				p.next = next;
				lastReturned.prev = null;
			}
			if(n == null) {
				tail = p;
				tail.next=  null;
			}else {
				n.prev = p;
			}
			if(next == null) {
				lastReturned = tail;
			}else {
				lastReturned = next.prev;
			}	
			
			size--;
			nextIndex--;
		}
	}
	
}
package list.doublylinkedlist.implementation;

import list.doublylinkedlist.implementation.DoublyLinkedList.ListIterator;

public class linkedMain {

	public static void main(String[] args) {
		DoublyLinkedList numbers = new DoublyLinkedList();

		numbers.addLast(10);
		numbers.addLast(20);
		numbers.addLast(30);
		ListIterator i = numbers.listIterator();
		while(i.hasNext()) {
			int number = (int)i.next();
			if(number == 20) {
				i.remove();
			}
		}
		System.out.println(numbers);
	}
}

 

 

반응형