LinkedList(1)

링크드 리스트 중 간단히 구현할 수 있는 단순 연결 리스트 이다

실상.. 간단하지는 않은 내용이다. 중간에 보변 reverse함수 부분은 유심히 보는 편이 좋을 듯 쉽다.

아래 그림은 단순 연결리스트 구조 이다.

class : ListNode

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

	
	public ListNode(String data){
		this.data = data;
	}
	
	public String getData(){
		return this.data;
	}
	
}

class: LinkedList

 

public class LinkedList {
	
	private ListNode head = null;
	
	public LinkedList(){
		this.head = null;
	}
	
	public void insertFirstNode(String data){
		ListNode newNode = new ListNode(data);
		
		if( this.head == null){
			this.head = newNode;
		}else{
			ListNode tmpListNode = head;
			this.head = newNode;
			newNode.link = tmpListNode;
		}
	}
	
	public void insertMiddleNode(ListNode pre, String data){
		ListNode newNode = new ListNode(data);
		newNode.link = pre.link;
		pre.link = newNode;
	}
	
	public void insertLastNode(String data){
		ListNode newNode = new ListNode(data);
		if(head == null) this.head = newNode;
		else{
			ListNode tmp = head;
			while(tmp.link != null) tmp = tmp.link;
			tmp.link = newNode;
		}
	}
	
	public void deleteLastNode(){
		ListNode pre,temp;
		if(head == null) return ;
		if(head.link == null) head = null;
		else{
			pre = head;
			temp = head.link;
			while(temp.link != null){
				pre = temp;
				temp = temp.link;
			}
			pre.link = null;
		}
	}
	
	public ListNode searchNode(String data){
		ListNode temp = this.head;
		while(temp != null){
			if(data.equals(temp.getData())) return temp;
			else temp = temp.link;
		}
		
		return temp;
	}
	
	public void reverseList(){
		ListNode next = head;
		ListNode current = null;
		ListNode pre = null;
		while(next != null){
			pre = current;
			current = next;
			next = next.link;
			current.link = pre;
		}
		
		head = current;
	}
	
	public void printList(){
		ListNode temp = this.head;
		System.out.printf("L = (");
		while(temp != null){
			System.out.printf(temp.getData());
			temp = temp.link;
			if(temp != null){
				System.out.printf(" ,");
			}
		}
		System.out.println(")");
	}	

}

 class : LinkedListMain

public class LinkedListMain {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LinkedList L = new LinkedList();
		System.out.println("add linkedList");
		L.insertLastNode("1");
		L.insertLastNode("2");
		L.insertLastNode("3");
		L.printList();
		
		System.out.println("add node(first)");
		L.insertFirstNode("first");
		L.printList();
		
		System.out.println("add node after 1");
		ListNode pre = L.searchNode("1");
		L.insertMiddleNode(pre, "ex");
		L.printList();
		
		System.out.println("reverse");
		L.reverseList();
		L.printList();
		
		System.out.println("delete");
		L.deleteLastNode();
		L.printList();
		

	}

}

실행 결과

 

참고 자료 및 소스 출처:

1. 위키

2. http://www.gurubee.net/pages/viewpage.action?pageId=1507898