[JAVA] 연결 리스트(Linked List)

//

//

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

• 연결될 다음 원소에 대한 주소를 저장해야하므로 <원소,주소>의 단위로 저장한다.

  이러한 단위 구조를 노드(node)라 함. <data+link>

삽입

1. 삽입할 새 노드를 만든다. 공백 노드 준비.

2. 새 노드의 데이터 필드값을 저장.

3. 삽입, 새 노드와 다음 노드 연결

4. 앞 노드와 새 노드 연결

삭제

1. 삭제할 원소의 앞 노드(선행자)를 찾음

2. 앞 노드의 링크 필드에 삭제할 노드의 링크 필드값을 저장한다. (삭제 노드 뒤의 링크 값 저장)

  package LinkedList;
  ​
  public class ListNode {
      private String data;
      public ListNode link;
      
      public ListNode(){
          this.data = null;
          this.link = null;
      }
      
      public ListNode(String data) {
          this.data = data;
      }
      
      public ListNode(String data, ListNode link) {
          this.data = data;
          this.link = link;
      }
  ​
      public String getData() {
          return data;
      }
  ​
  }

  
  package LinkedList;
  ​
  public class LinkedList {
      private ListNode head;
      
      public LinkedList(){
          head = null;
      }
      
      //노드를 중간에 삽입할 경우
      public void insertMiddleNode(ListNode pre, String data){
          ListNode newNode = new ListNode(data);
          //새로운 노드 생성 후 데이터 값 넣어줌
          newNode.link = pre.link;
          //새로운 노드의 링크가 앞의 노드가 가리키고 있던 링크를 가리킴
          pre.link = newNode;
          //앞의 노드가 새로운 노드를 가리킴
      }
      
      public void insertLastNode(String data){
          ListNode newNode = new ListNode(data);
          
          if(head == null){
              //공백 노드일 경우
              this.head = newNode;
          }
          else{
              ListNode temp = head;
              //리스트의 마지막 노드를 찾아야 하는데 마지막 노드의 링크는 null이다.
              //리스트의 노드들을 순회하는 임시 변수를 temp
              while(temp.link != null){
                  temp = temp.link;
              }
              temp.link = newNode;
          }
          
      }
      
      public void deleteLastNode(){
          ListNode pre,temp;
          
          if(head==null){
              //공백이면 수행 중단
              return;
          }
          if(head.link == null){
              head = null;
              //리스트가 공백인지 아닌지 확인
          }
          else{
              pre = head;
              temp = head.link;
              
              while(temp.link != null){
                  pre = temp;
                  temp = temp.link;
              }
              
              //링크 연결 끊기, 마지막 노드 삭제
              pre.link = null;
          }
      }
      
      
      public ListNode searchNode(String data){
          ListNode temp = this.head;
          while(temp != null){
              if(data == temp.getData()){
                  return temp;
              }
              else{
                  temp = temp.link;
              }
          }
          return temp;
      }
      
      public void printList(){
          ListNode temp = this.head;
          while(temp != null){
              System.out.print(temp.getData());
              temp = temp.link;
          }
      }
      
  ​
  }

  
  package LinkedList;
  import java.util.*;
  import java.io.*;
  ​
  public class LinkedListMain {
  ​
      public static void main(String[] args) {
          // TODO Auto-generated method stub
          LinkedList L = new LinkedList();
          
          System.out.println("노드 3개 삽입");
          L.insertLastNode("월");
          L.insertLastNode("화");
          L.insertLastNode("목");
          L.printList();
          
          System.out.println();
          
          System.out.println("화 노드 뒤에 수 노드 삽입하기");
          ListNode pre = L.searchNode("화");
          L.insertMiddleNode(pre, "수");
          L.printList();
          
          System.out.println();
          
          System.out.println("마지막 노드 삭제하기");
          L.deleteLastNode();
          L.printList();
      }
  ​
  }
  ​