단순 연결 리스트 (Singly Linked List)

Main.java

/**
 * 단순 연결 리스트 (Singly Linked List)
 * 
 * @author devetude
 */
public class Main {
	/**
	 * 메인 메소드
	 * 
	 * @param args
	 */
	public static void main(String args[]) {
		// 단순 연결 리스트 객체 생성
		SinglyLinkedList singlyLinkedList = new SinglyLinkedList();

		// 1, 2, 3을 담고 결과와 크기를 출력
		singlyLinkedList.addLast(1);
		singlyLinkedList.addLast(2);
		singlyLinkedList.addLast(3);
		System.out.println(singlyLinkedList.toString());
		System.out.println(singlyLinkedList.size());

		// 3번째 자리에 0 추가 후 결과와 크기, 0의 인덱스를 출력
		singlyLinkedList.add(2, 0);
		System.out.println(singlyLinkedList.toString());
		System.out.println(singlyLinkedList.size());
		System.out.println(singlyLinkedList.indexOf(0));

		// 3번째 자리에 있는 요소를 제거 후 결과와 크기 출력
		singlyLinkedList.remove(2);
		System.out.println(singlyLinkedList.toString());
		System.out.println(singlyLinkedList.size());
	}

	/**
	 * 단순 연결 리스트 클래스
	 * 
	 * @author devetude
	 */
	private static class SinglyLinkedList {
		private Node head;
		private Node tail;
		private int size = 0;

		/**
		 * 노드 이너 클래스
		 * 
		 * @author devetude
		 */
		private static class Node {
			public Object data;
			public Node next;

			/**
			 * 생성자
			 * 
			 * @param data
			 */
			public Node(Object data) {
				this.data = data;
				this.next = null;
			}
		}

		/**
		 * 맨 앞에 요소를 추가하는 메소드
		 * 
		 * @param data
		 */
		public void addFirst(Object data) {
			Node node = new Node(data);
			node.next = head;
			head = node;
			size++;

			if (head.next == null) {
				tail = head;
			}
		}

		/**
		 * 맨 뒤에 요소를 추가하는 메소드
		 * 
		 * @param data
		 */
		public void addLast(Object data) {
			Node node = new Node(data);

			if (size == 0) {
				addFirst(data);
			}

			else {
				tail.next = node;
				tail = node;
				size++;
			}
		}

		/**
		 * 해당 인덱스의 요소를 가져오는 메소드
		 * 
		 * @param index
		 * @return
		 */
		public Node get(int index) {
			Node node = head;

			for (int i = 0; i < index; i++) {
				node = node.next;
			}

			return node;
		}

		/**
		 * 해당 인덱스에 요소를 추가하는 메소드
		 * 
		 * @param index
		 * @param data
		 */
		public void add(int index, Object data) {
			if (index == 0) {
				addFirst(data);
			}

			else {
				Node tmp1 = get(index - 1);
				Node tmp2 = tmp1.next;
				Node node = new Node(data);
				tmp1.next = node;
				node.next = tmp2;
				size++;

				if (node.next == null) {
					tail = node;
				}
			}
		}

		/**
		 * 첫번째 요소를 삭제하는 메소드
		 * 
		 * @return
		 */
		public Object removeFirst() {
			Node tmp = head;
			head = tmp.next;

			Object data = tmp.data;
			tmp = null;
			size--;

			return data;
		}

		/**
		 * 해당 인덱스의 요소를 삭제하는 메소드
		 * 
		 * @param index
		 * @return
		 */
		public Object remove(int index) {
			if (index == 0) {
				return removeFirst();
			}

			else {
				Node tmp = get(index - 1);
				Node node = tmp.next;
				tmp.next = tmp.next.next;

				Object data = node.data;

				if (node == tail) {
					tail = tmp;
				}

				node = null;
				size--;

				return data;
			}
		}

		/**
		 * 크기를 구하는 메소드
		 * 
		 * @return
		 */
		public int size() {
			return this.size;
		}

		/**
		 * 해당 데이터의 인덱스를 가져오는 메소드
		 * 
		 * @param data
		 * @return
		 */
		public int indexOf(Object data) {
			Node node = head;
			int index = 0;

			while (node.data != data) {
				node = node.next;
				index++;

				if (node == null) {
					return -1;
				}
			}

			return index;
		}

		/**
		 * 내용을 출력하는 메소드
		 */
		public String toString() {
			Node node = head;

			StringBuilder sb = new StringBuilder();
			sb.append("[");

			for (int i = 0; i < size - 1; i++) {
				sb.append(node.data).append(", ");
				node = node.next;
			}

			sb.append(node.data);
			node = node.next;

			sb.append("]");

			return sb.toString();
		}
	}
}