Java단순연결리스트(Singly linked-list)/첫 번째 노드의 삽입.삭제

◆ 단순 연결 리스트 (Singly Linked-List)

연결 리스트의 가장 단순한 형태.
하나의 참조자만 가지고 있기 때문에 각 노드들은 하나의 노드만을 가리킬 수 있다.
그렇기 때문에 단방향성을 갖는다.
마지막 노드의 참조자가 null 값을 가리킬 때 리스트의 끝을 나타낸다.
헤더가 null 값을 가리킬 경우는 빈 리스트를 나타낸다.

이 번 포스팅에서는 첫 번째 노드의 삽입과 삭제에 관하여 쓰여졌습니다. ^^



-----------------------------------------------------------------------------------------------------------------------------------------------
◎ insertFirst() 메소드

새로운 노드를 리스트의 가장 첫 번째 자리에 삽입하는 메소드.

(a) 2를 삽입하기 전의 리스트

(b) 2를 삽입한 후의 리스트

-----------------------------------------------------------------------------------------------------------------------------------------------

◎ deleteFirst() 메소드
리스트의 가장 첫 번째 자리에 있는 노드를 삭제하는 메소드

(a) 3을 삭제하기 전의 리스트

(b) 3을 삭제한 후의 리스트

-----------------------------------------------------------------------------------------------------------------------------------------------
class LinkNode
{
 private int iData;  // 자료(키)
 private LinkNode nodeNext; // 다음 노드를 참조하는 포인터

 // 생성자
 public LinkNode(int iDataInput)
 {
  iData = iDataInput;
 }

 // 노드의 자료를 출력하는 메소드
 public void displayNode()
 {
  System.out.print(iData);
 }
 
 // 자료(키)에 접근하는 메소드
 public int getData()
 {
  return iData;
 }
 
 // 자료(키)를 변경하는 메소드
 public void setData(int inputData)
 {
  iData = inputData;
 }
 
 // 다음 노드 참조자에 접근하는 메소드
 public LinkNode getNodeNext()
 {
  return nodeNext;
 }
 
 // 다음 노드 참조자를 변경하는 메소드
 public void setNodeNext(LinkNode inputNode)
 {
  nodeNext = inputNode;
 }
}
//////////////////////////////////////////////////

////////// Sentinel Node Class ////////////////////
class LinkSentinelNode
{
 private LinkNode nodeFirst; // 첫 번째 노드를 참조하는 포인터
 
 // 생성자
 // - 리스트 초기 생성 시, 빈리스트이다
 public LinkSentinelNode()
 {
  nodeFirst = null;
 }
 
 // 첫 번째 노드를 참조하는 포인터 접근 메소드
 public LinkNode getNodeFirst()
 {
  return nodeFirst;
 }
 
 // 첫 번째 노드를 참조하는 포인터 접근 메소드
 public void setNodeFirst(LinkNode inputNode)
 {
  nodeFirst = inputNode;
 }
 
 // 빈 리스트인지 확인하는 메소드
 // - 빈 리스트일 경우 : true 반환
 // - 빈 리스트가 아닐 경우 : false 반환
 public boolean isEmpty()
 {
  return (nodeFirst == null);
 }
}
////////////////////////////////////////////////////

~~~~~~~~~~~~~~~~~~~~~~일때
class SimpleLinkedList
{
 // 헤드노드를 생성
 private LinkSentinelNode HeaderNode;
 
 // 생성자
 public SimpleLinkedList()
 {
  HeaderNode = new LinkSentinelNode();
 }


// 리스트의 첫 번째 자리로 노드를 삽입하는 메소드
 

public void insertFirst(int iKey)
 {
      //새로운 노드 생성
      LinkNode nodeNew = new LinkNode(iKey);
  
      // 새로운 노드는 기존의 첫 번째 노드를 참조
      nodeNew.setNodeNext(HeaderNode.getNodeFirst());
  
      // 헤더는 새로운 노드를 참조
     HeaderNode.setNodeFirst(nodeNew);
 }

// 리스트의 첫 번째 자리의 노드를 삭제하는 메소드

public LinkNode deleteFirst()
 {
  // 빈 리스트인지 확인
  if(HeaderNode.isEmpty() == false)
  {
   // 헤더노드가 가리키는 삭제 될(연결이 끊길) 첫 번째 노드를 선언
   LinkNode tempNode = HeaderNode.getNodeFirst();
   
   // 헤더는 두 번째 노드를 참조
   HeaderNode.setNodeFirst(HeaderNode.getNodeFirst().getNodeNext());
   
   return tempNode; // 삭제된 노드를 반환
  }
  else return null;   // 빈 리스트이면 null값 반환
 }

}

여기서 우리는 의문을 제기할 수 있습니다.
"분명 첫 번째 노드의 삭제라고 했는데~ 왜~ 그대로 있는거야?" ㅋ

노드의 삽입은 C/C++ 와 다름없이 문제없이 되지만,
노드의 삭제를 보면 Header 노드와 연결이 끊긴 3번 노드는 연결만 끊긴 상태로 그대로 있습니다. 

이러한 경우 C/C++ 에서는 프로그래머가 직접 처리(free)를 해줘야 메모리 누수(memory leak) 현상을 막을 수 있습니다.
하지만 자바에서는 쓰레기 수집(garbage collection) 프로세스가 알아서 연결이 끊어진 노드를 메모리에서 정리해주기 때문에 별도의 처리를 해주지 않아도 됩니다. ^^