pointer 방식 LinkedList 자바 구현 코드

 

 

포인터를 이용한 방식의 연결 리스트를 만든다. 

 

연결리스트에 필요한 노드 객체를 LinkedList 클래스 내부에 만든다. Node<E>는 데이터용 필드인 data와 자기 자신과 가은 클래스형을 참조하는 next를 필드로 갖는다. 

 

다음 노드를 참조하는 next를 뒤쪽 포인터라고 부를 수 있다. 각 노드의 필드 next에 넣어두는 것은 그 노드의 다음 노드에 대한 참조이다. 

 

public class PointerLinkedList<E> {
   
   
   private Node<E> head;
   private Node<E> current;
   
   
   static class Node<E>{
      private E data;
      private Node<E> next;

      public Node(E data, Node<E> next) {
         this.data = data;
         this.next = next;
      }
   }
}

 

그림으로 표현하자면 이와 같다. 

 

 

 

연결리스트 LinkedList<E>는 다음과 같은 두 필드를 갖는다.

- head: 머리 노드를 가리킨다

- current: 현재 선택한 노드를 가리킨다. 

 

이와 같은 노드를 통해 다음과 같은 연결을 구성한다. 

 

https://www.geeksforgeeks.org/types-of-linked-list/

 

 

초기 생성자 

 

public PointerLinkedList() {
   head = null;
   current = null;
}

 

명시적으로 null을 초기화해준다. 

 

노드가 1개인 연결리스트를 판단하는 방법 

 

head.next == null

 

 

노드가 2개인 연결 리스트를 판단하는 방법 

 

head.next.next == null

 

 

꼬리노드인지 판단하는 방법 

특정 Node<E> p가 리스트의 노드 중 하나를 가리킬 때 p가 가리키는 노드가 꼬리인지 판단한다. 

 

p.next ==null

 

 

 

 

search() 메서드 

 

 

검색 메서드를 구현한다. 

* 노드 스캔은 다음 두 조건 중 하나가 성립하면 종료된다.
* 1. 검색 조건을 만족하는 노드를 찾은 경우
* 2. 검색 조건을 만족하는 노드를 찾지 못하고 꼬리 노드를 지나가기 직전인 경우

 

이와 같은 과정을 수행하는 메서드를 다음과 같이 구현한다. 

 

/**
 * 노드 스캔은 다음 두 조건 중 하나가 성립하면 종료된다.
 * 1. 검색 조건을 만족하는 노드를 찾은 경우
 * 2. 검색 조건을 만족하는 노드를 찾지 못하고 꼬리 노드를 지나가기 직전인 경우
 *
 * 만약 pointer 값이 null이면 더 이상 스캔할 노드가 없음을 의미하므로 null을 리턴한다.
 * null이 아니라면 스캔을 시작하며 조건 1을 판단한다. 찾고자 하는 데이터와 해당하는 노드의 data 값을 비교한다.
 * 이와 같은 과정을 수핸한다.
 *
 * @param value : 검색할 때 key가 되는 데이터를 넣어둔 value
 * @param comparator 첫 번째 매개변수와 연결 리스트의 개별 노드 안에 있는 데이터를 비교하기 위한 compartor. 결과가 0이면 조건이 성립하는 것이다.
 * @return
 */

public E search(E value, Comparator<? super E> comparator){
   Node<E> pointer = head;

   while (pointer != null){
      if (comparator.compare(value, pointer.data) ==0){
         current = pointer;
         return pointer.data;
      }
      pointer = pointer.next;
   }
   return null;
}

 

먼저 pointer를 head로 초기화한다.

 

만약 pointer 값이 null이면 더 이상 스캔할 노드가 없음을 의미하므로 null을 리턴한다.
 null이 아니라면 스캔을 시작하며 조건 1을 판단한다. 찾고자 하는 데이터와 해당하는 노드의 data 값을 비교한다.
 이와 같은 과정을 반복하며 각 노드를 한 번씩 순회한다. 

 

 

 

addFirst() 메서드 

addFirst 메서드는 리스트의 머리에 노드를 삽입하는 메서드이다. 

 

public void addFirst(E value){
   Node<E> pointer =head;
   current = new Node<E>(value, pointer);
   head = current;
}

 

삽입 전의 머리 노드 A에 대한 포인터를 pointer에 대입한다. 

 

삽입할 노드를 생성하고, 해당 노드의 data는 인자로 받은 value, 해당 노드의 헤드는 삽입 전의 노드가 되도록 한다. 생성한 노드를 참조하도록 head 역시 업데이트 한다. 

 

 

 

addLast() 메서드 

 

public void addLast(E value){
   if (head == null){
      addFirst(value);
      return;
   }
   Node<E> pointer =head;
   while (pointer.next!=null){
      pointer= pointer.next;
   }
   current = new Node<E>(value,null);
   pointer = current;
}

 

리스트가 비어있는 경우 머리에 노드를 삽입한다. 비어있지 않는다면 꼬리에 삽입한다. 

 

머리 노드로 초기화한 pointer가 가리키는 노드를 계속해서 다음 노드를 가리키도록 반복하여 노드를 처음부터 차례로 스캔한다. pointer.next가 가리키는 노드가 null이 되면 이때 pointer가 가리키는 노드가 꼬리노드이다. 

 

 

removeFirst() 메서드

 

public void removeFirst(){
   if (head != null){
      current = head.next;
      head= current;
   }
}

remove 메서드는 머리 노드를 삭제하는 메서드이다. 리스트가 비어 있지 않은 경우에만 삭제를 실행한다. 머리 노드를 삭제하고 난 뒤 참조 관계를 두 번째 노드에 대한 참조 (head.next)로 대입시켜 주어, hear 가 가리키는 노드가 다음 노드가 되도록 한다.

 

 

 

removeLast() 메서드 

 

public void removeLast(){
   if (head != null){
      if(head.next==null){   // 머리 노드가 하나만 있는 경우
         removeFirst();
      } else{
         Node<E> pointer = head;
         Node<E> previous = head;
         
         while (pointer.next!=null){
            previous = pointer;
            pointer = pointer.next;
         }
         // while 문 종료시 pointer는 꼬리 노드를 가리키고 previous는 꼬리로부터 두 번째 노드를 나타낸다. 
         previous.next = null;
         current = previous;
      }
   }
}

 

리스트에 노드가 1개만 있는 경우 머리 노드를 삭제하는 것과 같으므로 removeFirst() 메서드로 수행한다. 

 

꼬리 노드와 꼬리 노드로부터 두 번째 되는 노드를 찾는다. 찾으면 꼬리 노드부터 두 번째 노드의 뒤쪽 포인터에 null을 대입한다. 즉, 자원을 null로 만들어 해제하는 것이다. 

 

 

 

 

 

전체 구현 및 예제 케이스 

 

 

 

package datastructure.list.pointlinkedlist;

import java.util.Comparator;

public class PointerLinkedList<E> {

   private Node<E> head;
   private Node<E> current;

   static class Node<E> {
      private E data;
      private Node<E> next;

      public Node(E data, Node<E> next) {
         this.data = data;
         this.next = next;
      }
   }

   public PointerLinkedList() {
      head = null;
      current = null;
   }

   /**
    * 노드 스캔은 다음 두 조건 중 하나가 성립하면 종료된다.
    * 1. 검색 조건을 만족하는 노드를 찾은 경우
    * 2. 검색 조건을 만족하는 노드를 찾지 못하고 꼬리 노드를 지나가기 직전인 경우
    * <p>
    * 만약 pointer 값이 null이면 더 이상 스캔할 노드가 없음을 의미하므로 null을 리턴한다.
    * null이 아니라면 스캔을 시작하며 조건 1을 판단한다. 찾고자 하는 데이터와 해당하는 노드의 data 값을 비교한다.
    * 이와 같은 과정을 수행한다.
    *
    * @param value      : 검색할 때 key가 되는 데이터를 넣어둔 value
    * @param comparator 첫 번째 매개변수와 연결 리스트의 개별 노드 안에 있는 데이터를 비교하기 위한 compartor. 결과가 0이면 조건이 성립하는 것이다.
    * @return
    */

   public E search(E value, Comparator<? super E> comparator) {
      Node<E> pointer = head;

      while (pointer != null) {
         if (comparator.compare(value, pointer.data) == 0) {
            current = pointer;
            return pointer.data;
         }
         pointer = pointer.next;
      }
      return null;
   }

   public void addFirst(E value) {
      Node<E> pointer = head;
      current = new Node<E>(value, pointer);
      head = current;
   }

   public void addLast(E value) {
      if (head == null) {
         addFirst(value);
         return;
      }
      Node<E> pointer = head;
      while (pointer.next != null) {
         pointer = pointer.next;
      }
      current = new Node<E>(value, null);
      pointer.next = current;
   }

   public void removeFirst() {
      if (head != null) {
         current = head.next;
         head = current;
      }
   }

   public void removeLast() {
      if (head != null) {
         if (head.next == null) {    // 머리 노드가 하나만 있는 경우
            removeFirst();
         } else {
            Node<E> pointer = head;
            Node<E> previous = head;

            while (pointer.next != null) {
               previous = pointer;
               pointer = pointer.next;
            }
            // while 문 종료시 pointer는 꼬리 노드를 가리키고 previous는 꼬리로부터 두 번째 노드를 나타낸다.
            previous.next = null;
            current = previous;
         }
      }
   }

   public void remove(Node p) {
      if (head == null) {
         if (p == head) {
            removeFirst();
         } else {
            Node<E> pointer = head;

            while (pointer.next != p) {
               pointer = pointer.next;
               if (pointer == null) {
                  return;
               }
            }
            pointer.next = p.next;
            current = pointer;
         }
      }
   }

   public void removeCurrentNode() {
      remove(current);
   }

   public void clear() {
      while (head != null) {
         removeFirst();
         ;
         current = null;
      }
   }

   public boolean next() {
      if (current == null || current.next == null) {
         return false;
      }
      current = current.next;
      return true;
   }

   public void printCurrentNode() {
      if (current == null) {
         System.out.println("선택한 노드가 없습니다");
      } else {
         System.out.println(current.data);
      }
   }

   public void dump() {
      Node<E> pointer = head;

      while (pointer != null) {
         System.out.println(pointer.data);
         pointer = pointer.next;
      }
   }

}

 

 

package datastructure.list.pointlinkedlist;

import java.util.Comparator;

public class PointerLinkedListTestSets {
   static class Data {
      static final int NO = 1;
      static final int NAME = 2;

      Integer no;
      String name;

      public String toString() {
         return String.format("%d %s", no, name);
      }

      public static final Comparator<Data> NO_ORDER = new NoOrderComparator();

      private static class NoOrderComparator implements Comparator<Data> {

         @Override
         public int compare(Data d1, Data d2) {
            return d1.no.compareTo(d2.no);
         }
      }

      public static final Comparator<Data> NAME_ORDER = new NameOrderComparator();

      private static class NameOrderComparator implements Comparator<Data> {

         @Override
         public int compare(Data d1, Data d2) {
            return d1.name.compareTo(d2.name);
         }
      }
   }
}

 

 

package datastructure.list.pointlinkedlist;

import datastructure.list.pointlinkedlist.PointerLinkedListTestSets.Data;

public class PointerLinkedListMain {

   public static void main(String[] args) {
      PointerLinkedList<Data> list = new PointerLinkedList<>();

      // 데이터 객체 생성
      Data data1 = new Data();
      data1.no = 3;
      data1.name = "Kim";

      Data data2 = new Data();
      data2.no = 2;
      data2.name = "Lee";

      Data data3 = new Data();
      data3.no = 1;
      data3.name = "Choi";

      // addFirst 메서드를 사용하여 데이터 객체를 리스트의 첫 번째에 추가
      list.addFirst(data1);
      list.addFirst(data2);
      list.addFirst(data3);

      // dump 메서드를 호출하여 리스트 출력
      System.out.println("리스트:");
      list.dump();
      System.out.println();

      // search 메서드를 호출하여 "Kim"을 검색
      System.out.println("Kim 검색");
      Data searchData = new Data();
      searchData.name = "Kim";
      Data result = list.search(searchData, Data.NAME_ORDER);
      if (result != null) {
         System.out.println("결과: " + result);
      } else {
         System.out.println("해당 요소 없음");
      }
      System.out.println();

      // addLast 메서드를 사용하여 데이터 객체를 리스트의 마지막에 추가
      Data data4 = new Data();
      data4.no = 4;
      data4.name = "Lee";
      list.addLast(data4);

      // dump 메서드를 호출하여 리스트 출력
      System.out.println("리스트:");
      list.dump();
      System.out.println();

      // removeFirst 메서드를 호출하여 첫 번째 노드 삭제
      System.out.println("첫 번째 노드 삭제:");
      list.removeFirst();
      list.dump();
      System.out.println();
   }
}

 

 

 

 

4번 요소를 추가한 직후 리스트 현황 

 

 

 

첫 번째 요소 삭제 후 리스트 현황