Linked List 특징

• 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조

• 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음

• 자료가 추가 될때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 연결함 (정해진 크기가 없음)

• 연결 리스트의 i 번째 요소를 찾는게 걸리는 시간은 요소의 개수에 비례 : O(n)

• jdk 클래스 : LinkedList

Linked List 구현하기

// MylistNode

package ch03;

public class MyListNode {
	// 노드 생성
	
	private String data; // 자료
	public MyListNode next; // 다음 노드 가리키는 포인터
	
	public MyListNode() {
		data = null;
		next = null;
	}
	
	public MyListNode(String data) {
		this.data = data;
		this.next = null;
	}
	
	public MyListNode(String data, MyListNode link) {
		this.data = data;
		this.next = link;
	}
	
	public String getData() {
		return data;
	}
}

package ch03;

public class MyLinkedList {
	
	private MyListNode head;
	int count;
	
	public MyLinkedList()
	{
		head = null;
		count = 0;
	}
	
	public MyListNode addElement ( String data)
	{
		MyListNode newNode;
		if ( head == null) {
			newNode = new MyListNode(data);
			head = newNode;
		}else {
			newNode = new MyListNode(data);
			MyListNode temp = head;
			// 처음 부터 순회 해서 맨 뒤 노드 까지 
			// 이 부분 한번더 짚고 넘어가자! 처음엔  이해 못했음! 
			while(temp.next != null) {
				temp = temp.next;
			
			}
			temp.next = newNode;
			
		}
		count++;
		return newNode;
	}
	
	public MyListNode insertElement(int position, String data)
	{
		int i;
		MyListNode tempNode = head;
		MyListNode preNode = null;
		
		MyListNode newNode = new MyListNode(data);
		
		if(position < 0 || position > count) {
			System.out.println("추가 할 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
			return null;
		}
		// 맨 앞에 추가 하는 경우! 
		if(position == 0) {
			newNode.next = head;
			head = newNode;	
		}else {
			/* head 즉 tempNode를 preNode에 대입한뒤 tempNode.next를 통해  
			다음 노드를 tempNode*/
			for (i=0; i < position; i++) {
				preNode = tempNode;
				tempNode = tempNode.next;
				}
			/* 기존 프리 노드가 가리키고 있던 넥스트 노드를  newNode.next에 대입한 후 
			  	preNode가 next를 통해 newNode를 가리키게 함 .  */
			newNode.next = preNode.next;
			preNode.next = newNode;
			}
		
		count++;
		return newNode;
			
	}
		
	
	public MyListNode removeElement(int position)
	{
		int i;
		MyListNode tempNode = head;
		
		if(position >= count ){
			System.out.println("삭제 할 위치 오류입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
			return null;
		}
		
		if(position == 0) {
			head = tempNode.next;
		}else {
			MyListNode preNode = null;
			for(i = 0; i < position; i++) {
				preNode = tempNode;
				tempNode = tempNode.next;
			}
			preNode.next = tempNode.next;
			
		}
		count --;
		System.out.println(position + "번째 항목 삭제되었습니다.");
		
		return tempNode;
		}
	
	public String getElement(int position)
	{
		int i;
		MyListNode tempNode = head;
		
		if(position >= count ){
			System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
			return new String("error");
		}
		
		if(position == 0){  //맨 인 경우

			return head.getData();
		}
		
		for(i=0; i<position; i++){
			tempNode = tempNode.next;
			
		}
		return tempNode.getData();
	}

	public MyListNode getNode(int position)
	{
		int i;
		MyListNode tempNode = head;
		
		if(position >= count ){
			System.out.println("검색 위치 오류 입니다. 현재 리스트의 개수는 " + count +"개 입니다.");
			return null;
		}
		
		if(position == 0){  //맨 인 경우

			return head;
		}
		
		for(i=0; i<position; i++){
			tempNode = tempNode.next;
			
		}
		return tempNode;
	}

	public void removeAll()
	{
		head = null;
		count = 0;
		
	}
	
	public int getSize()
	{
		return count;
	}
	
	public void printAll()
	{
		if(count == 0){
			System.out.println("출력할 내용이 없습니다.");
			return;
		}
		
		MyListNode temp = head;
		while(temp != null){
			System.out.print(temp.getData());
			temp = temp.next;
			if(temp!=null){
				System.out.print("->");
			}
		}
		System.out.println("");
	}
	
	public boolean isEmpty()
	{
		if(head == null) return true;
		else return false;
	}
	
}

public class MyLinkedListTest {

	public static void main(String[] args) {

		MyLinkedList list = new MyLinkedList();
		list.addElement("A");
		list.addElement("B");
		list.addElement("C");
		list.printAll();
		list.insertElement(3, "D");
		list.printAll();
		list.removeElement(0);
		list.printAll();
		list.removeElement(1);
		list.printAll();
						
		list.insertElement(0, "A-1");
		list.printAll();
		System.out.println(list.getSize());
		
		list.removeElement(0);
		list.printAll();
		System.out.println(list.getSize());
		
		list.removeAll();
		list.printAll();
		list.addElement("A");
		list.printAll();
		System.out.println(list.getElement(0));
		list.removeElement(0);
	}
}