[자료구조] Report : Linked List

자바로 링크드 리스트의 구현은 너무 쉽다. C언어의 포인터 변수만 생각하면 치가 떨리는데...

실제 소스 원본은 출력 메서드가 toString()이 아닌 printList()이다.

하지만 printList() 메서드 구현 대신에 toString()으로 구현했다.

class ListNode {
	String data;
	ListNode link;
	
	public ListNode() {
		data = null;
		link = null;
	}
	
	public ListNode(String data) {
		this.data = data;
		link = null;
	}
	
	public ListNode(String data, ListNode node) {
		this.data = data;
		link = node;
	}
}



public class LinkedList {
	private ListNode head;
	
	public void addLastNode(String data) {
		ListNode node = new ListNode();
		node.data = data;
		node.link = null;
		
		if (head == null) {
			head = node;
			return;
		}
		
		ListNode p = head;
		while (p.link != null) {
			p = p.link;
		}
		p.link = node;
	}
	
	
	
	public void reserve() {
		ListNode p = head;
		ListNode q = null;
		ListNode r = null;
		
		while (p != null) {
			r = q;
			q = p;
			p = p.link;
			q.link = r;
		}
		
		head = q;
	}
	
	
	
	public void deleteLastNode() {
		ListNode previousNode, currentNode;
		
		if (head == null)
			return;
		
		if (head.link == null) {
			head = null;
			return;
		}
		
		else {
			previousNode = head;
			currentNode = head.link;
			
			while(currentNode.link != null) {
				previousNode = currentNode;
				currentNode = currentNode.link;
			}
			previousNode.link = null;
		}
	}
	
	
	
	public String toString() {
		ListNode p = head;
		String str = "";
		
		while (p != null) {
			str += "(" + p.data + ")";
			p = p.link;
			if (p != null) {
				str += " - ";
			}
		}
		return str;
	}
	
	
	
	public void addFirstNode(String x) {
		ListNode newNode = new ListNode(x, head);
		head = newNode;
	}
	
	
	
	public void deleteFirstNode() {
		ListNode p = head;
		head = p.link;
	}
	
	
	
	public ListNode searchNode(String x) {
		ListNode p = head;
		
		while(p != null) {
			if(x.equals(p.data))
				return p;
			p = p.link;
		}
		return null;
	}
	
	
	
	public void insertNode(ListNode p, String x) {
		ListNode q = searchNode(x);
		
		if(q == null)
			return;
		
		ListNode r = q.link;
		q.link = p;
		p.link = r;
	}

	
	
	public static void main(String[] args) {
		LinkedList L = new LinkedList();
		L.addLastNode("A");
		L.addLastNode("B");
		L.addLastNode("C");
		System.out.println(L);
		
		L.reserve();
		System.out.println(L);
		
		L.deleteLastNode();
		System.out.println(L);
		
		L.addFirstNode("D");
		System.out.println(L);
		
		L.deleteFirstNode();
		System.out.println(L);
		
		ListNode p = new ListNode("E");
		L.insertNode(p, "C");
		System.out.println(L);
	}

}