32. 연결리스트(Linked List) 구현

0-1. 자료구조란 무엇인가? (Data Structure)
    1) 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현 방법들
    2) 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨
    3) 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음
    4) 여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 함

0-2. 선형 자료구조 (한 줄로 자료를 관리하기)
    1) Array(배열)
        - 정해진 크기의 메모리를 먼저 할당받아 사용
        - 자료의 물리적 위치와 논리적 위치가 같음

1. LinkedList 특징
    1) 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조
    2) 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음
    3) 자료가 추가될 때 노드 만큼의 메모리를 할당받고 이전 노드의 링크로 연결함
    4) JDK 클래스 : LinkedList
    5) 선형으로 자료를 관리
    6) 자료의 물리적 위치와 논리적 위치와 다를 수 있음
    7) 떨어진 곳에 존재하는 데이터를 화살표(포인터)로 연결해서 관리하는 데이터 구조

package kr.co.ezenac.ds;

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 String getData() {
		return data;
	}
}

package kr.co.ezenac.ds;

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 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 MyListNode insertElement(int position, String data) {
		int i;
		MyListNode tempNode = head;
		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 {
			MyListNode preNode = null;
			for(i=0; i<position; i++) {
				preNode = tempNode;
				tempNode = tempNode.next;
			}
			newNode.next = preNode.next;
			preNode.next = newNode;
		}
		count++;
		return newNode;
		
	}
}

package kr.co.ezenac.ds;

public class MyLinkedListTest {
	public static void main(String[] args) {
	
		MyLinkedList list = new MyLinkedList();
		list.printAll();
		
		System.out.println();
		
		list.addElement("A");
		list.addElement("B");
		list.addElement("C");
		list.printAll();
		
		System.out.println();
		
		list.insertElement(2, "D");
		list.printAll();
		
		System.out.println();
		
		list.insertElement(1, "E");
		list.printAll();
	}
}