DoublyLinkedList 구현코드

• List Interface 코드는 ArrayList 내용과 같다.

Node class

public class Node<E> {
	E data;
	Node<E> next;
	Node<E> prev;
	
	Node(E data){
		this.data = data;
		this.next = null;
		this.prev = null;
	}

}

DLinkedList class

import java.util.NoSuchElementException;

public class DLinkedList<E> implements List{
	private Node<E> head;
	private Node<E> tail;
	private int size;
	
	public DLinkedList() {
		this.head = null;
		this.tail = null;
		this.size = 0;	
	}
	
	private Node<E> search(int index){
		//index 예외처리
		if(index<0 || index>size) {
			throw new IndexOutOfBoundsException();
		}
		
		//인덱스가 앞에서 부터 검색하는 것이 효율적일 때
		if(size/2 > index) {
			Node<E> n= head;
			for(int i=0; i<index; i++) {
				n = n.next;
			}
			return n;
		}
		
		else {
			Node<E> n = tail;
			for(int i=size; i>index; i--) {
				n = n.prev;
			}
			return n;
		}
	}
	
	public void addFirst(E data) {
		Node<E> newNode = new Node<E>(data);
		Node<E> firstNode = head;
		
		newNode.next = firstNode;
		if(head != null) {
			firstNode.prev = newNode;
		}
		
		head = newNode;
		size++;
		
		//리스트에 방금 추가한 노드 하나만 있을 때
		if(head.next == null) {
			tail = head;
		}
	}
	
	@Override
	public boolean add(E value) {
		addLast(value);
		return true;
	}
	
	public void addLast(E data) {
		Node<E> newNode = new Node(data);
		Node<E> n = tail;
		
		if(size == 0) {
			addFirst(data);
		}
		
		n.next = newNode;
		newNode.prev = n;
		tail = newNode;
		size++;
	}
	
	
	public void add(E data, int index) {
		Node<E> newNode = new Node<E>(data);
		Node<E> NextN = search(index);
		Node<E> PrevN = NextN.prev;
		
		if(index<0 || index>size) {
			throw new IndexOutOfBoundsException();
		}
		if(index == 0 ) {
			addFirst(data);
		}
		if(index == size) {
			addLast(data);
		}
		
		PrevN.next = null;
		NextN.prev = null;
		
		newNode.prev = PrevN;
		newNode.next = NextN;
		
		PrevN.next = newNode;
		NextN.prev = newNode;
		
		size++;
	}
	
	public E remove() {
		if(head == null) {
			throw new NoSuchElementException();
		}
		
		E data = head.data;
		Node<E> firstNode = head;
		Node<E> nextNode = head.next;
		
		firstNode.data = null;
		firstNode.next = null;
		if(nextNode!= null) {
			nextNode.prev = null;
		}
		
		head = nextNode;
		size--;
		if(size == 0) {
			tail = null;
		}
		return data;
	}
	
	@Override
	public E remove(int index) {
		if(index<0 || index>size) {
			throw new IndexOutOfBoundsException();
		}
		if(index == 0) {
			E data = head.data;
			remove();
			return  data;
		}
		Node<E> currNode = search(index);
		Node<E> prevNode = search(index -1);
		Node<E> nextNode = search(index +1);
		E data = currNode.data;
		
		currNode.next = null;
		currNode.prev = null;
		currNode.data = null;
		
		prevNode.next = null;
		if(nextNode != null) {
			nextNode.prev = null;
			
			prevNode.next = nextNode;
			nextNode.prev = prevNode;
		}
		
		else { //삭제한 노드가 마지막 노드일 경우 예외처리
			tail = prevNode;
		}
		
		size--;
		return data;
	}
	
	@Override
	public boolean remove(Object data) {
		Node<E> n = head;
		for(int i=0; i<size; i++) {
			if(n.data.equals(data)) {
				remove(i);
				break;
			}
			n = n.next;
		}
		if(n==null) {
			return false;
		}
		
		return true;
	}
	/**
	 * https://st-lab.tistory.com/169?category=856997에서 작성된 코드
	 * 내가 생각한 알고리즘과 달라서 추가해놓음
	@Override
	public boolean remove(Object value) {
	 
		Node<E> prevNode = head;
		Node<E> x = head;		// removedNode 
			
		// value 와 일치하는 노드를 찾는다.
		for (; x != null; x = x.next) {
			if (value.equals(x.data)) {
				break;
			}
			prevNode = x;
		}
	 
		// 일치하는 요소가 없을 경우 false 반환 
		if(x == null) {
			return false;
		}
	 
		// 삭제하려는 노드가 head일 경우 remove()로 삭제
		if (x.equals(head)) {
			remove();
			return true;
		}
	    
		// remove(int index)와 같은 메커니즘으로 삭제
		else {
			Node<E> nextNode = x.next;
				
			prevNode.next = null;
			x.data = null;
			x.next = null;
			x.prev = null;
				
			if(nextNode != null) {
				nextNode.prev = null;
				
				nextNode.prev = prevNode;
				prevNode.next = nextNode;
			}
			else {
				tail = prevNode;
			}
	 
			size--;
			return true;
		}
	}
	**/
	
	public E get(int index) {
		Node<E> n = search(index);
		return n.data;
	}
	
	@Override
	public void set(int index, E value) {
		Node<E> n = search(index);
		n.data = null;
		n.data = value;
	}
	
	public int indexOf(Object data) {
		Node<E> n = head;
		int index = 0;
		for(; n != null; n = n.next) {
			if(n.data.equals(data)) {
				return index;
			}
			index++;
		}
		return -1;
	}
	
	public int lastindexOf(Object data) {
		Node<E> n = tail;
		int index = size;
		
		for(; n != null; n  =n.prev) {
			index--;
			if(n.data.equals(data)) {
				return index;
			}
		}
		return -1;
	}
	
	public boolean contains(Object data) {
		if(indexOf(data)>-1) {
			return true;
		}
		return false;
	}
	
	public int size() {
		return this.size;
	}
	
	public boolean isEmpty() {
		return size==0;
	}
	
	public void clear() {
		for(Node<E> n = head; n!=null;) {
			Node<E> nextNode = n.next;
			n.prev = null;
			n.next = null;
			n.data = null;
			n = nextNode;
		}
		
		head = tail = null;
		size = 0;
	}

}

https://st-lab.tistory.com/161?category=856997
내가 직접 코딩해보고 사이트를 확인하여 수정하는 방법으로 구현을 진행했음