Part2. 5-4 연결 리스트 (LinkedList) 구현하기

연결 리스트(LinkedList)  특징

 

• 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조
• 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음
• 자료가 추가 될때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 연결함 (정해진 크기가 없음)
• 연결 리스트의 i 번째 요소를 찾는게 걸리는 시간은 요소의 개수에 비례 : O(n)
• jdk 클래스 : LinkedList

 

public class MyListNode {

	private String data;       // 자료
	public MyListNode next;    // 다음 노드를 가리키는 링크
	
	public MyListNode(){     // 생성자 1 : 아무 입력이 없을 경우
		data = null;
		next = null;
	}
	
	public MyListNode(String data){   // 생성자 2 : 데이터를 입력했을 경우
		this.data = data;
		this.next = null;
	}
	
	public MyListNode(String data, MyListNode link){  // 생성자 3 : 데이터, 링크 모두 입력했을 경우
		this.data = data;
		this.next = link;
	}
	
	public String getData(){
		return data;
	}
}

 

 

연결리스트는 보통  (1번) head가 시작노드인 경우와 ,  (2) head포인터를 사용해서 head 다음부터 시작노드인 경우가 있는데
본 강의에서는 1번으로 구현했다.

 

 

연결리스트의 삽입과 삭제에서는  prev 노드(이전 노드) 가  중요하다,  얘를 알아야 한다

본강의에서 삽입함수는 2 유형이다.  (1) 맨 뒤에 노드를 추가하는 함수,  (2) 원하는 위치를 받아서 그 자리에 노드를 추가하는 함수

왜냐하면  삽입할 때는  1. 전 노드 ,  2. 다음 노드  이렇게  2개의 링크를 연결해야 하는데  이 둘 모두를  전 노드가 알고 있기 때문이다.  전 노드는 본인이니까 알고 ,  다음 노드는 본인이 가리키고 있으니까 알고 있다. 

그리고 연결은 다음 노드 먼저 해야 한다.   연결을 전 노드 먼저 해버리면  다음 노드를 가리키는 얘가 없어지기 때문이다.

 

삭제할 때는  단순 연결 리스트는  이중 연결 리스트와 다르게  연결하는 방향이 한 개이기 때문에

연결하는 주체가 전 노드이다.   방향 때문에 전 노드가 필요하다

 

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 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;
	}
	
    
	public MyListNode removeElement(int position)
	{
		int i;
		MyListNode tempNode = head;
		
		if(position >= count ){                // 위치 오류 (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;             // pre 노드 갱신
				tempNode = tempNode.next;
			}
			preNode.next = tempNode.next;
		}
		count--;                                // count 1 빼기
		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.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);
	}
}