ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • LinkedList(1)
    과거...../알고리즘 & 자료구조 2011. 4. 18. 11:01
    링크드 리스트 중 간단히 구현할 수 있는 단순 연결 리스트 이다

    실상.. 간단하지는 않은 내용이다. 중간에 보변 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



Designed by Tistory.