연결 리스트 (Linked list)

• 연결리스트는 연속된 노드들로 이루어진다.
• 노드는 자료를 저장하는 data feild와 다음 노드의 주소를 가리키는 link field로 이루어진다.

1. 단순 연결 리스트

노드 클래스

• 멤버변수 data는 String변수로써 노드에 데이터를 담는 역할을 한다.
• 멤벼변수 link는 다음 노드를 저장하는 역할로 사용되는 변수로, ListNode 자기 자신을 변수형태로 사용한다.
• 각각의 생성자는 매개변수의 종류에 따라 다른 역할로 사용된다.
• getData() : 해당 노드가 가지고 있는 data를 반환한다.

연결 리스트 클래스

• head : 리스트 안에서 가리키고 있는 자료의 ListNode이다.
• insertMiddleNode(ListNode, String) : 특정 노드 다음 노드에 자료를 삽입한다.
• insertLastNode(String) : 리스트의 마지막에 새로운 노드를 삽입한다.
• deleteLastNode() : 리스트의 마지막 노드를 삭제하는 메소드이다.
• searchNode(String) : String 매개변수를 입력으로 받아, 그 값에 해당하는 노드를 반환한다.

중간 노드 삽입 알고리즘

public void insertMiddleNode(ListNode pre, String data)
	{
		ListNode newNode = new ListNode(data);	// (1)
		newNode.link = pre.link;		// (2)
		pre.link = newNode;			// (3))
	}

• (1) 과정 : newNodeM를 생성하고, pre 노드는 리스트의 어딘가에 존재한다.
  
• (2) 과정 : newNode의 link에 pre.link를 대입함으로써, newNode의 다음 노드가 pre의 다음노드와 같게 한다.
  
• (3) 과정 : pre의 다음노드가 newNode를 가리키게 함으로써 최종적으로 pre와 node3 사이에 newNode가 삽입되도록 한다.
  
• 삽입 결과
  

마지막 노드 삽입 알고리즘

public void insertLastNode(String data)
{
	ListNode newNode = new ListNode(data);
	if(head == null)
	{
		this.head = newNode;            // (1)
	}
	else
	{
		ListNode temp = head;           // (2)
		while(temp.link != null)	
			temp = temp.link;       // (3)
		temp.link = newNode;	        // (4)	
	}
}

• (1) 과정 : 리스트가 비어있는 경우, 새로운 노드를 head 포인터에 바로 집어넣는다.
• (2) 과정 : 리스트의 끝을 탐색하기 위해, temp 노드를 생성한다.
• (3) 과정 : temp 노드를 뒤로 이동시키며, 리스트의 끝을 찾는다.
• (4) 과정 : temp 노드가 리스트의 끝에 도달했을때, newNode를 temp의 뒤에 연결시킨다.

마지막노드 삭제 알고리즘

public void deleteLastNode()
{
	ListNode pre;				
	ListNode temp;	        			
		
	if(head == null)                // (1)	
		return;					
	if(head.link == null)   	// (2)	
	{
		head = head.link;
	}
	else						
	{
		pre = head;	        	
		temp = head.link;       // (3)
		while(temp.link != null)// (4)
		{
			pre = temp;			
			temp = temp.link;	
		}
		pre.link = null;	//(5)
	}	
}

• (1) 과정 : 리스트가 비어있다면 아무것도 하지 않는다.
• (2) 과정 : 노드가 두개면 첫 노드를 마지막 노드로 변경하여, 두번째 노드를 지운다
• (3) 과정 : pre와 temp노드를 연달아 배치한다. temp는 삭제될 노드이고, pre는 마지막 노드가 될 노드이다.
• (4) 과정 : pre와 temp를 뒤로 한노드씩 이동시키며, temp가 마지막 노드가 되는 시점을 찾는다.
• (5) 과정 : while문 안의 temp = temp.link 에서 temp는 null이 되었으므로 삭제되었다. pre의 다음노드를 null로 지정하여 temp의 삭제를 마무리한다.