[자료구조] 링크드리스트 -JAVA

Urther·2021년 6월 29일
1

자료구조

목록 보기
2/4
post-thumbnail

자료구조에서 해쉬, 트리, 힙 등등 어려운 것들이 너무 많아요. 저는 특히나 링크드리스트가 너무 어렵게 느껴지더라구요!

개념부터 함께 정리하면서 더이상 링크드리스트를 어렵게 느끼지 맙시다 💪

Singly Linked List

단일 링크드 리스트

  • 노드 : 데이터 + 다음 노드 주소
  • 포인터 : 다음 노드 주소


크기가 정해진 배열의 한계를 극복할 수 있는 것이 링크드리스트이다. 데이터가 추가될 때 마다 노드를 하나씩 추가해주기만 하면 된다.

중간에 노드를 삽입/삭제하는 것도 가능하다.

① 객체 생성

: SingleLinkedList class를 만들고, Inner Class로 Node를 생성해준다.
아무런 Data가 없다면 head와 next는 null 상태가 되기 때문에 null 상태로 해주는 것이다.

class SingleLinkedList<T>{
  public Node<T> head=null;
  public class Node<T>{
      /*Node에 필요한 것은 data와 포인터*/
      T data;
      Node<T> next=null;

/*어떤 노드가 생성될 때 data라는 매개변수로 전달이 된다*/
      public Node(T data){
          this.data=data;
      }
  }

② 노드 Add 구현

  public void AddNode(T data){
      if(head==null) //head=null인 경우 : data가 없는 경우
          head=new Node<T>(data);
      else{ //data가 있는 경우
          Node<T> node=this.head;
          while(node.next!=null){
              /*node의 next가 null일 때 까지 검색. ->마지막 노드로 감*/
              node=node.next;
          }
          node.next=new Node<T>(data);
/*마지막 노드 next에 새로운 node 추가*/

      }

③ 노드 중간 Add 구현


:다만, 이렇게 하기 위해서는 앞에 있는 data의 위치를 알아야하기 떄문에 Search라는 기능이 필요한데 이 기능에 대한 구현은 다음 파트에서 설명하겠습니다.

    public void AddMiddle(T data, T indata){
        /*data는 들어갈 data 앞 숫자 data, indata는 넣고 싶은 data*/
        Node<T> searchNode=this.Search(data);

        if(searchNode==null)
            this.AddNode(indata);
          /*search해서 없다면, 맨 끝에 노드를 추가한다*/
        else{
            /*search해서 있는 경우*/
            Node<T> nextNode=searchNode.next;
            searchNode.next=new Node<T>(indata);
            searchNode.next.next=nextNode;
        }

    }

④ 노드 Search 구현

: 만약 찾는 노드가 있다면 node를 return해주고, 없다면 null을 리턴한다.

  public Node<T> Search(T data) {
      if(this.head!=null){
          Node<T> node=this.head;
          while(node.next!=null){
			 /*마지막 node까지 탐색해준다*/
              if(node.data==data)
                  return node;
              else
                  node=node.next;
		/*일치하는 data가 있다면 node 리턴,
		없다면 다음 노드로 넘겨준다.*/
          }
          return null;
      }
      else
	/*head==null인 경우는 데이터가 없는 경우이다*/
          return null;

⑤ 노드 삭제 구현

: 삭제할 노드를 찾고 삭제했다면 1 return, 삭제할 노드가 없다면 0을 return

public Integer DelNode(T data){
      if(this.head==null)
	  /*data가 없는 경우*/
          return 0;
      else{
	  /*data가 있는 경우*/
          Node<T> node=this.head;
          if(node.data==data){
		/*일치하는 data가 있는 경우, 현재 head를 head의 next 노드로 변경*/
              this.head=this.head.next;
              return 1;
          }
          else{
              while(node.next!=null){
                  if(node.next.data==data) {
                      node.next = node.next.next;
                      return 1;
                  }
                  else
                      node=node.next;
              }
              return 0;
          }
      }

⑥ 전체 코드

class SingleLinkedList<T>{
  public static void main(String[] args) {
      SingleLinkedList<Integer> my=new SingleLinkedList<Integer>();
      my.AddNode(3);
      my.AddNode(5);
      my.AddNode(4);
      //my.PrintAllNode();

      my.AddMiddle(1, 4);
      my.PrintAllNode();


  }

  public class Node<T>{
      /*Node에 필요한 것은 data와 포인터*/
      T data;
      Node<T> next=null;

      public Node(T data){
          this.data=data;
      }
  }
  public Node<T> head=null;
  /*초기에 데이터가 없기 때문에 head가 null*/

  /*노드 추가*/
  public void AddNode(T data){
      if(head==null) //head=null인 경우 : data가 없는 경우
          head=new Node<T>(data);
      else{ //data가 있는 경우
          Node<T> node=this.head;
          while(node.next!=null){
              /*node의 next가 null일 때 까지 검색. ->마지막 노드로 감*/
              node=node.next;
          }
          node.next=new Node<T>(data);

      }
  }
  public Node<T> Search(T data) {
      if(this.head!=null){
          Node<T> node=this.head;
          while(node.next!=null){
              if(node.data==data)
                  return node;
              else
                  node=node.next;
          }
          return null;
      }
      else
          return null;

  }
  /*중간에 들어갈 node*/
  public void AddMiddle(T data, T indata){
      /*data는 들어갈 data 앞 숫자 data, indata는 넣고 싶은 data*/
      Node<T> searchNode=this.Search(data);

      if(searchNode==null)
          this.AddNode(indata);
      else{
          Node<T> nextNode=searchNode.next;
          searchNode.next=new Node<T>(indata);
          searchNode.next.next=nextNode;
      }

  }
  public Integer DelNode(T data){
      if(this.head==null)
          return 0;
      else{
          Node<T> node=this.head;
          if(node.data==data){
              this.head=this.head.next;
              return 1;
          }
          else{
              while(node.next!=null){
                  if(node.next.data==data) {
                      node.next = node.next.next;
                      return 1;
                  }
                  else
                      node=node.next;
              }
              return 0;
          }
      }
  }
  /*노드 모두 출력*/
  public void PrintAllNode(){
      if(head!=null){
          Node<T>node=this.head;
          System.out.println(node.data);
          /*head에 있는 data 출력*/
          while(node.next!=null){
              node=node.next;
              System.out.println(node.data);
          }
      }
  }

}

Doubly Linked List

더블 링크드 리스트

: 99번째에 있는 노드의 데이터를 찾으려면 head에서부터 99번을 체크해줘야한다는 단점이 있다.
하지만, 더블 링크드 리스트를 사용한다면 prev, next 두 포인터를 사용하여 양쪽에서 탐색이 가능하기 때문에 유용하다

① 객체 생성

  public Node<T> head=null;
  public Node<T> tail=null;
  
  public class Node<T>{
      /*data,prev,next 필요*/
      T data;
      Node<T> prev=null;
      Node<T> next=null;

      public Node(T data){
          this.data=data;
      }
  }

② 노드 Add 구현

  public void Add_Node(T data){
      if(head==null) {
      /*데이터가 없는 상태*/
          head=new Node<T>(data);
          tail=this.head;
          /*head와 tail에 새로 추가되는 값을 넣어둔다.*/
      }
      else{
          /*데이터 값이 존재하는 경우*/
          Node<T> node=this.head;
          while(node.next!=null){
              /*마지막으로 이동*/
              node=node.next;
          }
          node.next=new Node<T>(data);
          node.next.prev=node;
          this.tail=node.next;
      }
  }

⑥ 전체 코드

public class test<T>{
  public Node<T> head=null;
  public Node<T> tail=null;

  public static void main(String[] args) {
      test<Integer> mytest=new test<Integer>();
      mytest.Add_Node(3);
      mytest.Add_Node(4);
      mytest.Add_Node(5);
      mytest.Add_middle(3, 2);
      //head 앞에 추가
      mytest.Add_middle(6, 9);
      mytest.Add_middle(4, 7);
      mytest.Print_All();
  }


  public class Node<T>{
      /*data,prev,next 필요*/
      T data;
      Node<T> prev=null;
      Node<T> next=null;

      public Node(T data){
          this.data=data;
      }
  }
  /*노드 추가 메소드*/
  public void Add_Node(T data){
      if(head==null) {
      /*데이터가 없는 상태*/
          head=new Node<T>(data);
          tail=this.head;
          /*head와 tail에 새로 추가되는 값을 넣어둔다.*/
      }
      else{
          /*데이터 값이 존재하는 경우*/
          Node<T> node=this.head;
          while(node.next!=null){
              /*마지막으로 이동*/
              node=node.next;
          }
          node.next=new Node<T>(data);
          node.next.prev=node;
          this.tail=node.next;
      }
  }
  /*노드 서치 메소드 head에서부터 검색*/
  public T SearchFromHead(T data){
      if(this.head==null){
          /*데이터가 없는 경우*/
          return null;
      }
      else{
          Node<T> node=head;
          while(node.next!=null){
              /*노드 마지막까지 이동*/
              if(node.data==data)
                  return node.data;
              else
                  node=node.next;
          }
          return null;
      }
  }
  /*노드 서치 메소드 tail부터 검색*/
  public T SearchFromTail(T data){
      if(this.head==null){
          return null;
      }
      else{
          Node<T> node=tail;
          while(node.prev!=null){
              if(node.data==data)
                  return node.data;
              else
                  node=node.prev;
          }
          return null;
      }
  }
  /*노드 중간 추가 메소드
  indata는 넣고자하는 data,
  data는 넣고자하는 위치 앞 data
   */
  public boolean Add_middle(T data, T indata){
      if(this.head==null){
          /*원래 있던 add 메소드로 마지막 삽입*/
          this.head=new Node<T>(indata);
          this.tail=head;
          return true;
      }
      else if(this.head.data==data){
          /* head 앞에 데이터를 넣고 싶을 때
          1. head를 indata로 변경, head의 prev를 indata next와 연결*/
          Node<T> NewHead=new Node<T>(indata);
          NewHead.next=this.head;
          this.head=NewHead;

          return true;
      }
      else{
          /* 중간에 있는 Data 앞에 넣고 싶을 때,
          1. 먼저 Data의 위치를 찾는다.
           */
          Node<T> node=this.head;
          while(node.next!=null){
              if(node.data==data){
                  /*찾는 data가 있을 경우*/
                  Node<T> PrevNode=node.prev;
                  PrevNode.next=new Node<T>(indata);
                  PrevNode.next.next=node;
                  /*next들 정리*/

                  PrevNode.next.prev=PrevNode;
                  node.prev=PrevNode.next;
                  return true;

              }
              else
                  node=node.next;
          }
          return false;
      }
  }
  public void Print_All(){
      if(head==null)
          System.out.println("no data");
      else{
          Node<T> node=head;
          System.out.println(node.data);
          while(node.next!=null){
              node=node.next;
              System.out.println(node.data);
          }
      }
  }
}
profile
Urther
이전해요 ☘️ https://mei-zy.tistory.com
이전 포스트

[자료구조] 해쉬 테이블 - JAVA

다음 포스트

[자료구조] 트리 1 - JAVA

0개의 댓글