[알고리즘 공부]4. 링크드리스트

링크드 리스트란, 객체 (흔히 노드라고 표현한다)

현재 자신의 데이터와 다음 노드를 가지고 있는 리스트이다.

처음에 시작점을 알아야 쭉 탐색이 가능하며, 중간에 수정이 들어갈때 불편하고, 

탐색을 하려면 처음 head로 시작해서 재귀로, 탐색을 이어 나가야 한다.

 

쉽게 구현해보면 아래와 같다.

 

이렇게 재귀를 통해서, 해당 노드에 대한 탐색을 할수있다.

노드는 이렇게 제네릭 타입으로 선언해서, 사용할수 있다.

 

그러면, 추가와 전체 노드 프린트하는 함수도 구해보자

 

전체적인 구조를 바꿔야 한다.

전체 링크드 리스트라는 구조 속에 노드들을 넣어야 하기 때문에, class 안에 class를 넣어야 한다.

우선 add함수를 구현해봤다.

제네릭 타입으로 변경했기 때문에, 해당 제네릭 타입으로 add를 했을 경우를 가정하였고

head가 null이라면, 해당 head에 값을 넣고, 그게 아니라면 node라는 변수를 head부터 nextnode로 바꿔가면서 null일때까지 반복

그리고 마지막으로 null일때 해당 nextNode값을 넣어주면된다.

 

 

print 함수도 비슷하다. head부터 시작해서 강제로 값을 프린트해주고,

해당 다음 노드를 while로 돌려가면서, nextNode로 바꿔주고, 맞다면, 해당 data를 출력해주면 된다.

 

만약에 특정 노드 사이에, 어떤 특정 노드를 넣어야 한다면 어떻게 될까?

아래와 같은 함수로 구현이 가능하다.

쉽게 말하면, 찾고자하는 node를 찾아서, 그 노드의 next를 신규 노드로, 그리고 신규 노드의 next를 기존의 next로 바꿔주면 된다.

public boolean searchNode(T isdata)
  {
      Node nd = head;
      while(nd.nextNode != null)
      {
          if(nd.data == isdata)
          return true;
          else
          nd = nd.nextNode;
      }
      return false;
      
  }
  public boolean addInsideNode(T data, T isdata)
  {
      boolean flag = this.searchNode(isdata);
      
      if(!flag)
      {
          addNode(data);
          
      }
      else{
          Node node = head;
          while(node.nextNode != null)
          {
              if(node.data == isdata){
              Node nd = node.nextNode;
              node.nextNode = new Node(data);
              node.nextNode.nextNode = nd;
              return true;
              }
              else{
                  node = node.nextNode;
              }
          } 
      }
       return false;
      
  }
  

이 두가지 함수로, 추가하면 쉽게 찾아서 사이에 껴넣을수 있다.

 

중간에 삭제, 추가가 일어난다면 정말 비효율 적이다

 

그다음에 나오는 내용인, 더블 링크드 리스트를 한번 보자

더블 링크드 리스트는, 노드의 다음 차수만 가지고있는 게 아니라, 앞뒤로 전부다 가지고 있는 것이다.

다음 노드만 가지고  다음으로만 갈수있는 노드를 싱글 링크드 리스트라고 하고 앞뒤로 다 가능한 것을 더블 링크드 리스트라고 한다.

while문 응용은 자유롭게 하면 될 것같고, 해당 방식으로 선언해서 함수 만들어서 사용하면 된다.

 

 

next를 사용하거나, head를 사용할떄 tail과 prev를 동시에 체크 및 관리를 하면된다.