JAVA Node로 LinkedList 구현하기

JAVA내에서는 LinkedList가 내장되어 있지만 Node 클래스를 만들어서 LinkedList를 구현해보았다.

package javaBasic;

class Node {
	
	// 멤버 변수 선언
	private int element;
	private Node pre;
	
	// 변수에 대한 getter,setter 메소드 생성
	public int getElement() {
		return element;
	}
	public void setElement(int element) {
		this.element = element;
	}
	public Node getPre() {
		return pre;
	}
	public void setPre(Node pre) {
		this.pre = pre;
	}
}
class LinkedList{
	Node head = new Node();
	Node tail = new Node();
	int size=0;
    
    // 해당하는 Node를 리턴하는 메소드
	public Node getNode(int element) {
		if(size==0) return null;
		else {
			Node temp = head.getPre();
			while(!temp.equals(tail)) {
				if(temp.getElement()==element) return temp;
				temp = temp.getPre();
			}
			return null;
		}
	}
	
    // node를 추가하는 메소드
	public int add(int element) {
		if(getNode(element)!=null) return -1;
		Node node = new Node();
		node.setElement(element);
		if(size==0) {
			head.setPre(node);
			node.setPre(tail);
		} else {
			Node temp = head.getPre();
			head.setPre(node);
			node.setPre(temp);
		}
		size++;
		return element;
	}
	
    // Node를 제거하는 메소드
	public int removeNode(int element) {
		Node node;
		Node next = null;
		if(size==0) return 0;
		if((node = getNode(element))!=null) {
			Node temp = head.getPre();
			int ans = node.getElement();
			while(temp.getElement()!=element) {
				next = temp;
				temp = temp.getPre();
			}
			while(temp.getPre()!=tail) {
				temp.setElement(temp.getPre().getElement());
				next = temp;
				temp = temp.getPre();
			}
			next.setPre(tail);
			size--;
			return ans;
		} else {
			return -1;
		}
	}
    
    // 가장 최근에 추가된 Node의 element를 리턴하는 메소드
    public int top() {
		if(size==0) return -1;
		return head.getPre().getElement();
	}
    
    // LinkedList의 크기를 리턴하는 메소드
	public int getSize() {
		return size;
	}
    
    // LinkedList를 출력하는 메소드
	public String toString() {
		Node temp = head.getPre();
		String ans = "";
		while(!temp.equals(tail)) {
			ans = ans + temp.getElement()+" ";
			temp = temp.getPre();
		}
		return ans;
	}
}


public class Test014 {
	public static void main( String[] args ) {
		LinkedList list = new LinkedList();
		list.add(5);
		list.add(8);
		list.add(3);
		list.add(2);
		list.add(4);
		list.removeNode(3);
		list.removeNode(8);
		System.out.println(list.top());	// 4
		System.out.println(list.getSize());// 3
		System.out.println(list.toString());// 4 2 5
	}
}

LinkedList 작동 원리

LinkedList의 각 노드들은 이전 노드를 가리키는 pre변수와 노드의 속성인 element변수를 갖는다.

 

pre변수는 이전 노드를 가리켜야하므로 자기 자신의 type인 Node로 참조형 변수를 만들어야 한다.

 

1. getNode 메소드

	public Node getNode(int element) {
		if(size==0) return null;
		else {
			Node temp = head.getPre();
			while(!temp.equals(tail)) {
				if(temp.getElement()==element) return temp;
				temp = temp.getPre();
			}
			return null;
		}
	}

getNode 메소드는 요청된  element가 LinkedList에 있는지 head부터 tail까지 탐색한 후에 해당되는 Node가 있으면

그 Node를 리턴하고 없으면 null을 리턴한다. 만약  LinkedList의 크기가 0이라면 null을 리턴한다. 

 

초기에 temp를 head의 pre Node를 가리키게 한다. 그 후 만약 temp가 가리키는 노드의 element가 요청된  element와 같다면 temp를 리턴하고, 그렇지 않다면 temp를 pre Node로 다시 이동시킨다.

 

2. add 메소드

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

add 메소드는 매개변수에 요청된 element로 생성된 새로운 Node를 추가하는 메소드이다.

일단 getNode메소드를 사용하여 List내에 요청된 element값과 같은 Node가 있는지 검사를 한다.

같은 Node가 있다면 추가를 하지 않고 -1을 리턴한다.

 

List의 크기가 0이라면 head의 pre를 추가되는 Node를 가리키게한 후 추가되는 Node의 pre가 tail을 가리키게 한다.

 

그렇지 않다면 head의 pre는 추가되는 Node를 가리키게한 후 추가되는 Node의 pre는 기존의 head 의 pre가 가리켰던 Node를 가리키게 한다.

 

이를 구현하기 위해 temp에 기존에 head의 pre가 가리키는 노드를 담아두고  추가되는 Node의 pre가 temp를 가리키게 한다.

 

3. removeNode 메소드

public int removeNode(int element) {
		Node node;
		Node next = null;
		if(size==0) return 0;
		if((node = getNode(element))!=null) {
			Node temp = head.getPre();
			int ans = node.getElement();
			while(temp.getElement()!=element) {
				next = temp;
				temp = temp.getPre();
			}
			while(temp.getPre()!=tail) {
				temp.setElement(temp.getPre().getElement());
				next = temp;
				temp = temp.getPre();
			}
			next.setPre(tail);
			size--;
			return ans;
		} else {
			return -1;
		}
}

remove 메소드는 요청된 element를 갖는 Node를 제거하는 메소드다. 

getNode로 Node를 찾지 않은 이유는 getNode로 Node를 찾아도 찾은 Node의 next Node를 알 수 없기 때문이다.

 

remove를 구현하기 위해서는 제거하고자 하는 Node의 next Node 의 pre Node가 제거하고자 하는 Node의 pre Node를 가리키게 해야한다. 

 

따라서 head 노드부터 탐색을 시작해서 제거하고자 하는 Node와 그 next Node를 찾아서 remove를 해야한다.

 

4. top, getSize 메소드

public int top() {
	if(size==0) return -1;
	return head.getPre().getElement();
}
    
// LinkedList의 크기를 리턴하는 메소드
public int getSize() {
	return size;
}

 top은 LinkedList에서 가장 앞에 있는 Node를 리턴하는 메소드다.

getSize는 LinkedList의 크기를 리턴하는 메소드다.