JAVA Node로 Doubly Linked List 구현하기

이전에 다음과 같이 Node를 연결하여 일반적인 Linked List를 구현했다.

 

https://rightx2.tistory.com/11

JAVA Node로 LinkedList 구현하기

이번에는 Node를 양방향으로 연결하여 Doubly Linked List를 구현할 것이다.

 

이전에 구현했던 Linked List와 차이점

 

1. Node 멤버변수 중 next가 추가됐다.

: pre변수만 있던 Linked List에 next 변수를 추가해 node를 추가하거나 제거할 때 Node의 탐색시간을 줄일 수 있다.

 

2. Node의 element변수의 타입을 int에서 Generic으로 변경했다.

: Node element 타입을 Generic으로 변경함으로써 단순히 int 타입의 변수뿐만 아니라 객체들로 Linked List를 구현할 수 있다.

 

package javaBasic;

class Node<T>{
	private Node<T> pre;
	private Node<T> next;
	private T element;
	
	public Node<T> getPre() {
		return pre;
	}
	public void setPre(Node<T> pre) {
		this.pre = pre;
	}
	public Node<T> getNext() {
		return next;
	}
	public void setNext(Node<T> next) {
		this.next = next;
	}
	public T getElement() {
		return element;
	}
	public void setElement(T element) {
		this.element = element;
	}
}

class DoublyLinkedList<T>{
	private Node<T> head = new Node<T>();
	private Node<T> tail = new Node<T>();
	private int size = 0;
	
	public DoublyLinkedList(){
		head.setPre(tail);
		tail.setNext(head);
	}
	public Node<T> getNode(T element) {
		Node<T> temp = tail;
		while(!temp.equals(head)) {
			if(temp.getElement()==element) return temp;
			temp = temp.getNext();
		}
		return null;
	}
	
	public T add(T element) {
		if(getNode(element)!=null) return null;
		Node<T> node = new Node<T>();
		node.setElement(element);
		if(size==0) {
			head.setPre(node);
			node.setNext(head);
			tail.setNext(node);
			node.setPre(tail);
			size++;
		} else {
			Node<T> temp = head.getPre();
			head.setPre(node);
			node.setNext(head);
			node.setPre(temp);
			temp.setNext(node);
			size++;
			
		}return element;
	}
	
	public T remove(T element) {
		Node<T> node = null;
		
		if((node=getNode(element))==null) return null;
		
		node.getPre().setNext(node.getNext());
		node.getNext().setPre(node.getPre());
		node.setNext(null);
		node.setPre(null);
		node.setElement(null);
		size--;
		return element;
	} 
	
	public int getSize() {
		return size;
	} 
	
	public Node<T> top() {
		if(size==0) return null;
		return head.getPre();
	}
	
	public Node<T> bottom() {
		if(size==0) return null;
		return tail.getNext();
	}
	
	public String toString() {
		Node<T> temp = tail.getNext();
		String str = "";
		while(!temp.equals(head)) {
			str = str + temp.getElement() + " ";
			temp = temp.getNext();
		}
		return str;
	}
}

public class Test014 {
	public static void main( String[] args ) {
    
		DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
        	DoublyLinkedList<String> strList = new DoublyLinkedList<>();

		list.add(15);
		list.add(31);
		list.add(71);
		list.add(44);
		list.add(53);
		list.add(26);
        
        	list.remove(71);
		list.remove(26);
        
        	strList.add("kane");
        	strList.add("Thomas");
        	strList.add("Jane");
        	strList.add("Tom");
        
        	strlist.remove("Jane");
        
		System.out.println(list.getSize());//4
		System.out.println(list.toString());// 15 31 44 53
		System.out.println(list.top().getElement());// 53
		System.out.println(list.bottom().getElement());// 15
        
        	System.out.println(strList.getSize());//3
		System.out.println(strList.toString());// Kane Thomas Tom
		System.out.println(strList.top().getElement());// Tom
		System.out.println(strList.bottom().getElement());// Kane
	}
}

 

1. Node 클래스

class Node<T>{
	private Node<T> pre;
	private Node<T> next;
	private T element;
	
	public Node<T> getPre() {
		return pre;
	}
	public void setPre(Node<T> pre) {
		this.pre = pre;
	}
	public Node<T> getNext() {
		return next;
	}
	public void setNext(Node<T> next) {
		this.next = next;
	}
	public T getElement() {
		return element;
	}
	public void setElement(T element) {
		this.element = element;
	}
}

: element 변수를 제네릭타입으로 선언함으로써 element의 객체화를 가능하게한다. pre는 현재노드의 이전노드를 가리키게하고 next는 현재노드의 다음노드를 가리키게 한다.

 

2. getNode 메소드

 

	public Node<T> getNode(T element) {
		Node<T> temp = tail;
		while(!temp.equals(head)) {
			if(temp.getElement()==element) return temp;
			temp = temp.getNext();
		}
		return null;
	}

 

: temp노드를 생성해서 초기에는 list의 tail노드를 가리키케 한다.

만약 temp노드의 element가 매개변수로 받은 element와 일치한다면 해당 노드를 리턴하고 그렇지 않다면 temp노드를 temp노드의 next를 가리키게 한다. 만약 head 노드까지 탐색했을 때 일치하는 노드가 없다면 null을 리턴한다.

 

3. add 메소드

public T add(T element) {
		if(getNode(element)!=null) return null;
		Node<T> node = new Node<T>();
		node.setElement(element);
		if(size==0) {
			head.setPre(node);
			node.setNext(head);
			tail.setNext(node);
			node.setPre(tail);
			size++;
		} else {
			Node<T> temp = head.getPre();
			head.setPre(node);
			node.setNext(head);
			node.setPre(temp);
			temp.setNext(node);
			size++;
			
		}return element;
}

: 리스트에 추가하고자 하는 element가 존재한다면 null을 리턴하면서 노드를 추가하지 않는다.

 

리스트의 size가 0인 경우

1. head의 pre가 추가되는 노드를 가리키게 한다.

2. 추가되는 노드의 next가 head를 가리키게 한다.

3. tail의 next가 추가되는 노드를 가리키게 한다.

4. 추가되는 노드의 pre가 tail을 가리키게 한다. 

5. 리스트의 사이즈를 증가시킨다.

 

일반적인 경우

1. 임시로 생성한 temp노드가 head의 pre노드를 가리키게 한다.

2. head의 pre가 추가되는 노드를 가리키게 한다.

3. 추가되는 노드의 next가 head를 가리키게 한다.

4. temp의 next가 추가되는 노드를 가리키게 한다.

5. 추가되는 노드의 pre가 temp를 가리키게 한다. 

5. 리스트의 사이즈를 증가시킨다.

 

4. remove 메소드

	public T remove(T element) {
		Node<T> node = null;
		
		if((node=getNode(element))==null) return null;
		
		node.getPre().setNext(node.getNext());
		node.getNext().setPre(node.getPre());
		node.setNext(null);
		node.setPre(null);
		node.setElement(null);
		size--;
		return element;
	} 

1. 제거할 노드를 가리키기위해 node변수명을 갖는 노드를 생성한다.

2. getNode함수를 사용해서 만약 제거할 노드가 리스트에 존재하지 않는다면 null을 리턴하고 존재한다면 node가 해당노드를 가리키게 한다.

3. node의 이전노드의 next노드를 node의 다음노드를 가리키게 한다.

4. node의 다음노드의 pre노드를 node의 이전노드를 가리키게 한다.

5. node를 제거해야하기 때문에 노드의 모든 변수를 null값으로 초기화 시킨다.

6. 리스트의 size를 감소시킨다.

7. 제거된 노드의 element를 리턴한다.

 

5. top, bottom 메소드

	public Node<T> top() {
		if(size==0) return null;
		return head.getPre();
	}
	
	public Node<T> bottom() {
		if(size==0) return null;
		return tail.getNext();
	}
	

1. top메소드는 가장 최근에 추가된 node를 리턴하는 메소드로 head의 이전노드를 리턴한다.

2. bottom메소드는 가장 먼저 추가된 node를 리턴하는 메소드로 tail의 다음노드를 리턴한다.