자바로 짜는 List

19 April 2018

Algorithm

이번엔 List를 짜보았다. Java에는 ArrayList라는 훌륭한 API를 제공해주고 있어서 실제로 이렇게 짜서 하는 경우는 없지만 어떻게 돌아가는지 알려면 한번쯤 짜봐야 한다고 생각했다. List와 지금까지 해봤던 Stack과 Queue의 다른 점은 List는 각 아이템마다 position이 있어서, get(int position) 함수를 사용하여 해당 순서의 아이템을 바로 뽑을 수 있다. 해당 position의 아이템을 삭제하면 해당 뒷 노드 앞 노드가 알아서 합쳐지는 등 연결리스트 개념을 알고리즘으로 풀어낸 것이라고 볼 수 있다.

이번 구현에는 기존까지 작업하였던 Stack과 Queue에서 사용하였던 구현 방식을 토대로 작업하였는데, 쉽게 말해서 마지막 노드(lastNode)를 사용해서 해당 포지션을 탐색하고 삭제하는 작업을 하였다. 사실상 Stack과 Queue의 난이도 업그레이드 버전이다.

List 개념도 및 get() 구현방식

public class Node
{
	private Object object;	//요건 Queue때랑 똑같다
	private Node prev;
	private Node next;
	public Node(Object object, Node prev, Node next)
	{
		super();
		this.object = object;
		this.prev = prev;
		this.next = next;
	}
	public Object getObject()
	{
		return object;
	}
	public void setObject(Object object)
	{
		this.object = object;
	}
	public Node getPrev()
	{
		return prev;
	}
	public void setPrev(Node prev)
	{
		this.prev = prev;
	}
	public Node getNext()
	{
		return next;
	}
	public void setNext(Node next)
	{
		this.next = next;
	}
}

public class List
{
	private int size;
	private Node lastNode;
	public List()
	{
		this.size = 0;
		this.lastNode = null;
	}
	/**
		한쪽 방향에서 삽입이 이뤄진다
	*/
	public void add(Object object)
	{
		Node node = new Node(object, lastNode, null);
		if(size != 0)	//최초 삽입이 아닐 경우
		{
			lastNode.setNext(node);
		}
		lastNode = node;
		this.size++;
		System.out.println(object.toString()+" is added, size : "+size);
	}
	public void remove(int position)
	{
		if(this.size < position)
			throw new NoSuchElementException("Position's item is empty");
		else
		{
			Node findNode = get(position);
			this.size--;
			System.out.println(findNode.getObject() + " is removed, size : "+size);
			//찾은 Node를 기준으로 삭제 후 서로 연결해준다
			Node prevFindNode = findNode.getPrev();
			Node nextFindNode = findNode.getNext();

			if(prevFindNode == null)	//List Item이 가장 첫번째일 경우 예외처리
			{
				prevFindNode = findNode;
			}
			prevFindNode.setNext(nextFindNode);

			if(nextFindNode!=null)	 
			{
				nextFindNode.setPrev(prevFindNode);
			}
			else
			{
				//List Item이 가장 마지막일 경우 예외처리
				lastNode = prevFindNode;
			}
		}
	}
	public Node get(int position)
	{
		if(this.size <= position)
			throw new NoSuchElementException("Position's item is empty");
		else
		{
			Node findNode = lastNode;
			//lastNode에서 Position 만큼 거슬러 올라간다
			for(int i = 0; i < (size-position-1); i++)
			{
				findNode = findNode.getPrev();
			}
			return findNode;
		}
	}

	@Override
	public String toString()
	{
		StringBuilder sb = new StringBuilder();
		sb.append("[ ");
		for(int i= 0; i<size; i++)
		{
			sb.append(get(i).getObject().toString() + " ");
		}
		sb.append("]");
		return sb.toString();
	}
}

이 Queue에서 하는 일은 다음과 같다

add(Object object) : 데이터를 한방향으로 추가한다
remove(int position) : 해당 position의 Node를 삭제하고 양옆 노드를 연결시킨다
get(int position) : 해당 position의 Node를 반환한다
toString() : 보기 편하게 현재 List 아이템들을 출력해준다

결과

package github.bobos.list;

public class Main
{
	public static void main(String[] args)
	{
		List list = new List();
		list.add(1);
		list.add(2);
		list.add(3);
		list.add(4);
		System.out.println(list.toString());
		list.remove(0);
		list.remove(2);
		System.out.println(list.toString());
		list.remove(3);
	}
}

1 is added, size : 1
2 is added, size : 2
3 is added, size : 3
4 is added, size : 4
[ 1 2 3 4 ]
1 is removed, size : 3
4 is removed, size : 2
[ 2 3 ]
Exception in thread "main" java.util.NoSuchElementException: Position's item is empty
	at github.bobos.list.List.remove(List.java:28)
	at github.bobos.list.Main.main(Main.java:16)

자바로 짜는 Queue

devbobos