개발자로 살아남기

이진 탐색 트리 (Binary Search Tree, BST)

이진 탐색 트리 (Binary Search Tree, BST)

• 이진 트리의 일종
• 데이터를 트리에 저장하는 규칙에 따라야 함
• 노드에 저장된 키 값은 유일해야 함
• 왼쪽 자식 노드 키 > 부모 노드 키 > 오른쪽 노드 키
• 삽입할 데이터가 부모 노드보다 작으면 왼쪽, 크면 오른쪽에 삽입
• 왼쪽과 오른쪽의 서브 트리도 이진 탐색 트리
  

  

이진 탐색 트리 구현 방법

• 삽입
  부모 노드와 삽입할 데이터를 비교해서 삽입할 데이터가 더 크면 오른쪽에 추가하고, 더 작으면 왼쪽에 추가한다. 단, 비교할 대상이 없을때까지 내려가야 한다.
  

  

• 탐색
  삽입과 마찬가지로 찾고자하는 데이터가 부모 노드보다 작으면 왼쪽, 크다면 오른쪽으로 탐색한다. 단, 탐색 도중 데이터를 찾았거나 마지막까지 탐색했다면 탐색을 중지한다.
  
  
• 삭제
  임의의 노드(데이터)를 삭제하는 경우 삭제 후에도 이진 탐색 트리가 유지되도록 빈자리를 채워야 한다. 삭제에는 아래 3가지 경우가 있어 각각 다른 방식으로 삭제를 해야한다. 
  1) 단말 노드를 삭제할 경우
  2) 하나의 자식 노드를 가진 노드를 삭제할 경우
  3) 두 개의 자식 노드를 가진 노드를 삭제할 경우
  
  

1) 단말 노드를 삭제할 경우

2) 하나의 자식 노드를 가진 노드를 삭제할 경우

10을 삭제할 경우 자식 노드 13을 10의 위치로 복사하고 13의 노드를 삭제한다.

3) 두 개의 자식 노드를 가진 노드를 삭제할 경우

13을 이동시킨 이유는 이진 탐색 트리는 부모 노드의 왼쪽은 부모 노드보다 작은값, 오른쪽은 큰 값이 되어야 하므로 13을 이동시켰음. 18을 이동시켜도 상관없음

구현

• [BinaryTree.java]
  

  package BinarySearchTree;
  
  public class BinaryTree {
      BTreeNode createBTreeNode() {
          BTreeNode newNode = new BTreeNode();
          newNode.leftNode = null;
          newNode.rightNode = null;
  
          return newNode;
      }
  
      int getData(BTreeNode node) {
          return node.data;
      }
  
      void setData(BTreeNode node, int data) {
          node.data = data;
      }
  
      BTreeNode getLeftSubTree(BTreeNode node) {
          return node.leftNode;
      }
  
      BTreeNode getRightSubTree(BTreeNode node) {
          return node.rightNode;
      }
  
      void createLeftSubTree(BTreeNode parent, BTreeNode child) {
          if (parent.leftNode != null){
              parent.leftNode = null;
          }
  
          parent.leftNode = child;
      }
  
      void createRightSubTree(BTreeNode parent, BTreeNode child) {
          if (parent.rightNode != null) {
              parent.rightNode = null;
          }
  
          parent.rightNode = child;
      }
  
      // 중위 순회
      void InorderTraverse(BTreeNode node) {
          if (node == null){
              return;
          }
  
          InorderTraverse(node.leftNode);
          System.out.println(node.data);
          InorderTraverse(node.rightNode);
      }
  
      // 전위 순회
      void PreorderTraverse(BTreeNode node) {
          if (node == null) {
              return;
          }
  
          System.out.println(node.data);
          PreorderTraverse(node.leftNode);
          PreorderTraverse(node.rightNode);
      }
  
      // 후위 순회
      void PostorderTraverse(BTreeNode node) {
          if (node == null) {
              return;
          }
  
          PostorderTraverse(node.leftNode);
          PostorderTraverse(node.rightNode);
          System.out.println(node.data);
      }
  }​

• [BTreeNode.java]
  

  package BinarySearchTree;
  
  public class BTreeNode {
      int data;
      BTreeNode leftNode;
      BTreeNode rightNode;
  }

• [BST.java]
  

  package BinarySearchTree;
  
  public class BST extends BinaryTree {
      private BTreeNode rootNode = null;
  
      public void insert(int data) {
          // 첫 데이터가 추가됐을 때
          if (rootNode == null) {
              rootNode = new BTreeNode();
              setData(rootNode, data);
              return;
          }
  
          BTreeNode curNode = rootNode;
          BTreeNode parentNode = null;
          // 현재 노드에 데이터가 없을때까지 반복
          while(curNode != null) {
              // 키는 유일해야 하므로 중복값이 있을 경우 빠져나옴
              if (getData(curNode) == data) {
                  return;
              }
  
              // 자식노드가 없을 때 데이터 추가를 위해 부모노드의 값을 유지하고 있어야 함
              parentNode = curNode;
              // 현재 노드의 값이 삽입할 데이터의 값보다 크면 현재 노드의 왼쪽 서브트리에 데이터가 있다는 것이 되므로 왼쪽을 반환
              if (getData(curNode) > data) {
                  curNode = getLeftSubTree(curNode);
              }
              else {
                  curNode = getRightSubTree(curNode);
              }
          }
  
          BTreeNode newNode = new BTreeNode();
          setData(newNode, data);
  
          // 부모 노드의 값이 삽입할 데이터보다 크면 부모 노드의 왼쪽에 데이터를 삽입해야 하므로 왼쪽에 데이터를 등록함
          if (getData(parentNode) > data) {
              createLeftSubTree(parentNode, newNode);
          }
          else {
              createRightSubTree(parentNode, newNode);
          }
      }
  
      // 단순 검색 (존재 유무만 판단함)
      public boolean search(int data) {
          BTreeNode curNode = rootNode;
  
          // 현재 가리키고 있는 노드가 null일 때까지 반복해서 확인
          while(curNode != null) {
  
              // 현재 노드의 값이 찾으려는 대상과 같으면 true
              if (getData(curNode) == data) {
                  return true;
              }
              // 현재 노드의 값이 찾으려는 대상의 값보다 크면 왼쪽 서브트리에 찾을 대상이 있다는 것이므로 현재 노드의 왼쪽을 반환
              else if (getData(curNode) > data){
                  curNode = getLeftSubTree(curNode);
              }
              else {
                  curNode = getRightSubTree(curNode);
              }
          }
  
          return false;
      }
  
      public boolean remove(int data) {
          // 삭제할 노드가 있는지 검색
          BTreeNode deleteNode = rootNode;
          BTreeNode deleteParentNode = null;
          while (deleteNode != null && getData(deleteNode) != data) {
              deleteParentNode = deleteNode;
  
              if (getData(deleteNode) > data) {
                  deleteNode = getLeftSubTree(deleteNode);
              }
              else {
                  deleteNode = getRightSubTree(deleteNode);
              }
          }
  
          // 찾는 데이터가 없다면 false
          if (deleteNode == null) {
              return false;
          }
  
          // 단말노드 삭제 시
          if (getLeftSubTree(deleteNode) == null && getRightSubTree(deleteNode) == null) {
              if (getLeftSubTree(deleteParentNode) == deleteNode) {
                  removeLeftSubTree(deleteParentNode);
              }
              else {
                  removeRightSubTree(deleteParentNode);
              }
          }
          // 자식노드가 하나인 노드 삭제 시
          else if (getLeftSubTree(deleteNode) == null || getRightSubTree(deleteNode) == null) {
              // 삭제할 데이터가 부모노드의 왼쪽에 있는지 오른쪽에 있는지 확인
              if (getLeftSubTree(deleteParentNode) == deleteNode) {
                  // 부모노드의 왼쪽값이 null이 아니면 왼쪽에 데이터가 있다는 것이므로
                  // 부모노드의 왼쪽과 삭제할 데이터의 왼쪽을 연결해 이어줌
                  if (getLeftSubTree(deleteNode) != null) {
                      deleteParentNode.leftNode = deleteNode.leftNode;
                  }
                  // 부모노드의 오른쪽값이 null이 아니면 오른쪽에 데이터가 있다는 것이므로
                  // 부모노드의 왼쪽과 삭제할 데이터의 오른쪽을 연결해 이어줌
                  else {
                      deleteParentNode.leftNode = deleteNode.rightNode;
                  }
              }
              else {
                  if (getRightSubTree(deleteNode) != null) {
                      deleteParentNode.rightNode = deleteNode.rightNode;
                  }
                  else {
                      deleteParentNode.rightNode = deleteNode.leftNode;
                  }
              }
          }
          // 자식노드가 둘인 노드 삭제 시
          else {
              // 이진 탐색 트리의 특성 상 부모의 오른쪽 서브트리에서 가장 작은 값으로 부모노드를 변경해주어야 함
              BTreeNode replaceNode = getRightSubTree(deleteNode);
              BTreeNode replaceParentNode = deleteNode;
              while(getLeftSubTree(replaceNode) != null) {
                  replaceParentNode = replaceNode;
                  replaceNode = getLeftSubTree(replaceNode);
              }
              // 위 로직을 거치면 deleteNode는 삭제할 노드 대신 들어갈 노드를 가리키고,
              // deleteParentNode는 대신 들어갈 노드의 부모를 가리키게 됨.
  
              setData(deleteNode, getData(replaceNode));
  
              // 대신 들어갈 노드의 부모 노드의 왼쪽이 대신 들어갈 노드라면
              // 대신 들어갈 노드의 오른쪽 서브트리를 부모 노드의 왼쪽으로 연결한다.
              if (getLeftSubTree(replaceParentNode) == replaceNode) {
                  replaceParentNode.leftNode = replaceNode.rightNode;
              }
              // 대신 들어갈 노드의 부모 노드의 오른쪽이 대신 들어갈 노드라면
              // 부모 노드의 오른쪽을 대신 들어갈 노드의 오른쪽 노드와 연결한다.
              else {
                  replaceParentNode.rightNode = replaceNode.rightNode;
              }
          }
  
          return true;
      }
  
      private void removeLeftSubTree(BTreeNode node) {
          BTreeNode removeNode = node.leftNode;
          node.leftNode = null;
          removeNode = null;
      }
  
      private void removeRightSubTree(BTreeNode node) {
          BTreeNode removeNode = node.rightNode;
          node.rightNode = null;
          removeNode = null;
      }
  
      // 중위 순회
      void InorderTraverse(BTreeNode node) {
          if (node == null){
              return;
          }
  
          InorderTraverse(node.leftNode);
          System.out.print(node.data + " ");
          InorderTraverse(node.rightNode);
      }
  
      public void showAll() {
          InorderTraverse(rootNode);
          System.out.println();
      }
  }​

• [BSTMain.java]
  

  package BinarySearchTree;
  
  public class BSTMain {
      public static void main(String[] args) {
          BST bst = new BST();
  
          bst.insert(5); bst.insert(8);
          bst.insert(1); bst.insert(6);
          bst.insert(4); bst.insert(9);
          bst.insert(3); bst.insert(2);
          bst.insert(7);
          bst.showAll();
  
          bst.remove(3); bst.showAll();
          bst.remove(8); bst.showAll();
          bst.remove(1); bst.showAll();
          bst.remove(6); bst.showAll();
      }
  }​

• 테스트
  

  

두 개의 자식 노드가 있는 노드를 삭제할 때 헷갈린 부분이 있었다.

처음에는 대체할 부모의 노드의 왼쪽은 당연히 대체할 노드일 것이라고 생각해서 위 코드가 이해가 되지 않았다. 그러나 아래 그림을 삭제에 대입해서 생각해보니 당연한 얘기였다.

12를 삭제 시 위 코드의 if문에 들어가게 되고, 8을 삭제 시 else 문을 들어가게 된다. 데이터는 12, 8, 4, 6, 9, 10, 17, 13, 21 을 넣고 테스트해보면 된다. 

버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)

• 가장 단순한 정렬 알고리즘
• 인접한 요소와 정렬 기준(오름차순, 내림차순)대로 교환
• 안정 정렬 (stable sort)
   : 정렬 후에도 같은 값들 끼리의 순서가 보장됨을 의미
• 제자리 정렬 (in-place sort)
   : 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미
• 정렬한 데이터의 개수가 적을때는 나쁘지 않은 속도를 보임

버블 정렬 방법 (오름차순 기준)

• 첫 번째 사이클이 끝나면 맨 마지막 값이 정렬되고, 두 번째 사이클이 끝나면 뒤에서 두 번째의 값이 정렬된다. 이같은 과정을 계속 반복하면 최종적으로 정렬이 된다. 

버블 정렬의 성능

• 시간복잡도
  최악의 경우 : O(n^2)
  최선의 경우 : O(n)
  
  
• 최악의 경우 : 모든 데이터가 역순인 경우 (5, 4, 3, 2, 1)
  5를 정렬하기 위해서는 n-1번 비교 및 교환해야하고, 4를 정렬하기 위해서는 n-2번 비교 및 교환해야 한다.
  즉, 5를 정렬할 때 4번, 4를 정렬할 때 3번, 3을 정렬할 때 2번, 1과 2를 정렬할 때 1번의 비교 및 교환을 거치게 되므로 비교 횟수는 4 + 3 + 2 + 1회가 된다. 
  따라서, 데이터가 n개일 때 총 비교횟수는 (n-1) + (n-2) + (n-3) + ... + 2 + 1 이 되므로 등차수열의 합에 따라 1/2n(n-1)이 되며 빅-오는 최고차항을 가지기 때문에 O(n^2)이 된다.
  
  
• 최선의 경우 : 모든 데이터가 이미 정렬된 경우 (1, 2, 3, 4, 5)
  한 번도 교환이 이루어지지 않았다면 이미 정렬된 상태이므로 n번 비교 후 반환되어 O(n) 이 된다.
  
  

기본 구현

• 기본 int형 배열 정렬 구현
  [BubbleBasic.java]
  

  package Sort.Bubble;
  
  /**
   * 단순히 int형 배열만 오름차순 또는 내림차순으로 정렬하는 경우
   */
  public class BubbleBasic {
      private boolean isDescending = false;
  
      /**
       * @param arr int형 배열
       * @param isDescending 내림차순 및 오름차순 선택
       */
      public static void sort(int[] arr, boolean isDescending) {
          // 이미 정렬이 되어있는지 확인하기 위한 변수
          boolean isAlreadySorted = true;
          int n = arr.length;
  
          // 정렬할 값을 선택하는 반복문
          for(int i=0; i<n-1; i++) {
              // 정렬할 값과 나머지 값들을 비교하기 위한 반복문
              // 이미 정렬이 완료된 데이터는 비교대상에서 제외해야 하므로 n-i-1
              for(int j=0; j<n-i-1; j++) {
                  // 정렬되지 않았다면
                  if (!isSortTwoElements(arr[j], arr[j + 1], isDescending)) {
                      // 데이터를 교환한다.
                      swap(arr, j, j + 1);
                      // 스왑을 했다면 초기 배열 상태가 정렬되지 않았다는 것이므로 false로 변경
                      isAlreadySorted = false;
                  }
              }
  
              // 한 번도 교환이 발생하지 않았다면 이미 정렬된 데이터이므로 반복문을 빠져나온다.
              if (isAlreadySorted) {
                  break;
              }
          }
      }
  
      /**
       *
       * @param arr 데이터 배열
       * @param idx1 교환할 인덱스
       * @param idx2 교환할 인덱스
       */
      private static void swap(int[] arr, int idx1, int idx2) {
          int tmp = arr[idx1];
          arr[idx1] = arr[idx2];
          arr[idx2] = tmp;
      }
  
      /**
       *
       * @param cmp1 비교할 값
       * @param cmp2 비교할 값
       * @param isDescending 내림차순 및 오름차순 선택
       * @return 내림차순의 경우 cmp1이 작을 경우 false, 그렇지 않으면 true
       *         오름차순의 경우 cmp1이 작을 경우 true, 그렇지 않으면 false
       */
      private static boolean isSortTwoElements(int cmp1, int cmp2, boolean isDescending) {
          // 내림차순일 경우
          if (isDescending) {
              if (cmp1 < cmp2) {
                  return false;
              }
              else {
                  return true;
              }
          }
          // 오름차순일 경우
          else {
              if (cmp1 < cmp2) {
                  return true;
              }
              else {
                  return false;
              }
          }
      }
  }​

• BubbleBasic.java 테스트 및 실행시간 측정
  

  package Sort.Bubble;
  
  public class BubbleBasicMain {
      private static final int MAX_COUNT = 10;
  
      public static void main(String[] args) {
          int[] arr = new int[MAX_COUNT];
          for(int i=0; i<MAX_COUNT; i++) {
              // 0 ~ MAX_COUNT 범위내의 난수를 생성
              arr[i] = (int)(Math.random() * MAX_COUNT);
          }
  
          // 배열은 참조형 이므로 arr을 넘길 경우 arr값이 변경되기 때문에 복사본을 생성한 후 테스트
          int[] ascArrTest = arr.clone();
          System.out.println("정렬 전 데이터");
          for(int i : ascArrTest) {
              System.out.println(i);
          }
          System.out.println();
  
          BubbleBasic.sort(ascArrTest, false);
          System.out.println("오름차순 정렬 후 데이터");
          for(int i : ascArrTest) {
              System.out.println(i);
          }
          System.out.println();
  
          int[] descArrTest = arr.clone();
          BubbleBasic.sort(descArrTest, true);
          System.out.println("내림차순 정렬 후 데이터");
          for(int i : descArrTest) {
              System.out.println(i);
          }
  
          // 시간복잡도 측정 (오름차순 기준)
          long start = 0;
          long end = 0;
  
          int[] bestTimeComplexityArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
          start = System.nanoTime();
          BubbleBasic.sort(bestTimeComplexityArray, false);
          end = System.nanoTime();
          System.out.println("최선의 경우 오름차순 시간 : " + (end - start) + "ns");
  
          int[] worstTimeComplexityArray = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
          start = System.nanoTime();
          BubbleBasic.sort(worstTimeComplexityArray, false);
          end = System.nanoTime();
          System.out.println("최악의 경우 오름차순 시간 : " + (end - start) + "ns");
      }
  }​

  
  
  
• 결과
  

  정렬 전 데이터 2 6 1 7 7 6 0 6 1 0 오름차순 정렬 후 데이터 0 0 1 1 2 6 6 6 7 7 내림차순 정렬 후 데이터 7 7 6 6 6 2 1 1 0 0 최선의 경우 오름차순 시간 : 3805ns 최악의 경우 오름차순 시간 : 18532ns

클래스 비교를 위한 구현

• 클래스의 특정 값을 이용한 정렬 코드 구현
  [BubbleAdvanced.java]
  

  package Sort.Bubble;
  
  import java.util.Comparator;
  
  public class BubbleAdvanced {
      public static <T> void sort(T[] arr) {
          Comparable<? super T> comp;
          boolean isAlreadySorted = true;
          int n = arr.length;
  
          for(int i=0; i<n-1; i++) {
              for(int j=0; j<n-i-1; j++) {
                  comp = (Comparable<? super T>)arr[j];
                  if (comp.compareTo(arr[j + 1]) > 0) {
                      swap(arr, j, j + 1);
                      isAlreadySorted = false;
                  }
              }
  
              if (isAlreadySorted){
                  break;
              }
          }
      }
  
      /**
       *
       * @param arr 데이터 배열
       * @param idx1 교환할 인덱스
       * @param idx2 교환할 인덱스
       */
      private static <T> void swap(T[] arr, int idx1, int idx2) {
          T tmp = arr[idx1];
          arr[idx1] = arr[idx2];
          arr[idx2] = tmp;
      }
  
      public static <T> void sort(T[] arr, Comparator<? super T> comparator) {
          boolean isAlreadySorted = true;
          int n = arr.length;
  
          for(int i=0; i<n-1; i++) {
              for(int j=0; j<n-i-1; j++) {
                  if (comparator.compare(arr[j], arr[j + 1]) > 0) {
                      swap(arr, j, j + 1);
                      isAlreadySorted = false;
                  }
              }
  
              if (isAlreadySorted){
                  break;
              }
          }
      }
  }​

• BubbleAdvanced 테스트
  

  package Sort.Bubble;
  
  import java.util.Comparator;
  
  public class BubbleAdvancedMain {
      private static final int MAX_COUNT = 10;
  
      public static void main(String[] args) {
          Integer[] arr = new Integer[MAX_COUNT];
          for (int i = 0; i < MAX_COUNT; i++) {
              // 0 ~ MAX_COUNT 범위내의 난수를 생성
              arr[i] = (int) (Math.random() * MAX_COUNT);
          }
  
          // 배열은 참조형 이므로 arr을 넘길 경우 arr값이 변경되기 때문에 복사본을 생성한 후 테스트
          Integer[] ascArrTest = arr.clone();
          System.out.println("정렬 전 데이터");
          for (int i : ascArrTest) {
              System.out.println(i);
          }
          System.out.println();
  
          BubbleAdvanced.sort(ascArrTest);
          System.out.println("오름차순 정렬 후 데이터");
          for (int i : ascArrTest) {
              System.out.println(i);
          }
          System.out.println();
  
          Integer[] descArrTest = arr.clone();
          System.out.println("내림차순 정렬 후 데이터");
          BubbleAdvanced.sort(descArrTest, new Comparator<Integer>() {
              @Override
              public int compare(Integer o1, Integer o2) {
                  if (o1 < o2) {
                      return 1;
                  } else if (o1 == o2) {
                      return 0;
                  } else {
                      return -1;
                  }
              }
          });
          for (int i : descArrTest) {
              System.out.println(i);
          }
          System.out.println();
  
          // 클래스의 특정값을 이용한 정렬 가능
          class Student {
              String name;
              int age;
  
              public Student(String name, int age) {
                  this.name = name;
                  this.age = age;
              }
  
              @Override
              public String toString() {
                  return "name='" + name + '\'' +
                          ", age=" + age;
              }
          }
  
          System.out.println("클래스 정렬 전 데이터");
          Student[] students = new Student[5];
          students[0] = new Student("아이언맨", 11);
          students[1] = new Student("헐크", 4);
          students[2] = new Student("토르", 15);
          students[3] = new Student("블랙위도우", 13);
          students[4] = new Student("캡틴", 4);
          for(Student student : students) {
              System.out.println(student.toString());
          }
          System.out.println();
  
          System.out.println("클래스 정렬 후 데이터");
          BubbleAdvanced.sort(students, new Comparator<Student>() {
              @Override
              public int compare(Student o1, Student o2) {
                  if (o1.age < o2.age) {
                      return -1;
                  }
                  else if (o1.age == o2.age) {
                      return 0;
                  }
                  else {
                      return 1;
                  }
              }
          });
  
          for(Student student : students) {
              System.out.println(student.toString());
          }
      }
  }​

• 결과
  

  정렬 전 데이터 7 0 0 9 4 4 6 0 5 0 오름차순 정렬 후 데이터 0 0 0 0 4 4 5 6 7 9 내림차순 정렬 후 데이터 9 7 6 5 4 4 0 0 0 0 클래스 정렬 전 데이터 name='아이언맨', age=11 name='헐크', age=4 name='토르', age=15 name='블랙위도우', age=13 name='캡틴', age=4 클래스 정렬 후 데이터 name='헐크', age=4 name='캡틴', age=4 name='아이언맨', age=11 name='블랙위도우', age=13 name='토르', age=15

단순 연결 리스트

단순 연결 리스트

• 크기가 변경 불가능한 배열의 단점을 극복 (배열은 정적인 메모리 구성)
• 크기가 정해져있지 않음 (동적인 메모리 구성)
• 데이터들을 Node로 관리 (Node : data, 다음 노드의 주소값으로 이루어져 있음)
• 리스트는 데이터의 저장 순서를 유지해야하는 자료구조가 아님
• Node
  

  

• 리스트의 구성
  

  

• 필요한 Node들
  head : 리스트의 머리를 가리킴
  tail : 리스트의 꼬리를 가리킴
  cur : 데이터의 조회에 사용됨
  

  

  head에 데이터 추가 시
  장점 : tail 노드가 불필요
  단점 : 저장 순서가 유지되지 않음
  
  tail에 데이터 추가 시
  장점 : 저장 순서가 유지됨
  단점 : tail 노드가 필요
• 데이터 추가
  tail 또는 head쪽에 데이터 추가 후 tail 또는 head가 가리키는 값 변경
  ex) tail에 데이터 추가 시 
  

  

• 데이터 조회
  cur Node를 이용해 조회
  ex) data2 조회
  

  

• 데이터 삭제
  삭제할 노드를 가리키고 있는 노드의 next 값을 삭제할 노드가 가진 next 값으로 변경
  

  

• 추상 자료형 (ADT)
  

  자료형	반환값	내용
  initialize()	void	리스트 초기화
  insert(Node)	boolean	리스트에 데이터 저장
  next()	Node	현재 가리키고 있는 노드의 다음 노드
  remove()	Node	현재 가리키고 있는 노드를 삭제
  count()	int	현재 리스트에 있는 데이터의 개수

구현

• 디렉토리 구조
  

  

• 인터페이스 구현
  다형성을 위해 List관련 메소드를 인터페이스로 구현
  

  package List;
  
  // 다형성을 위해 List를 인터페이스로 생성
  public interface List {
      // 리스트 초기화
      void initialize();
      // 리스트에 데이터 삽입 (어떤 값이 올 지 모르므로 Object를 인자로 받음)
      boolean insert(Object data);
      // 첫 번째 데이터를 가리키도록 하며 값을 반환
      Object first();
      // 현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
      Object next();
      // 현재 참조하고 있는 데이터를 지움
      Object remove();
      // 리스트에 저장된 데이터의 개수를 반환
      int count();
  }​

• 단일 연결 리스트 구현
  실제 단일 연결 리스트 구현
  

  package List.LinkedList.Single;
  import List.List;
  
  public class SingleLinkedList implements List {
      public class Node {
          Object data;
          Node nextNode;
  
          public Node(Object data, Node nextNode){
              this.data = data;
              this.nextNode = nextNode;
          }
  
          public Node() {
              this.data = null;
              this.nextNode = null;
          }
      }
  
      Node head = null;
      Node tail = null;
      Node cur = null;
  
      Node newNode = null;
      int dataCount = 0;
  
      @Override
      public void initialize() {
          head = null;
          tail = null;
          cur = null;
          newNode = null;
      }
  
      @Override
      public boolean insert(Object data) {
          try {
              newNode = new Node(data, null);
  
              if (head == null) {
                  head = newNode;
              } else {
                  tail.nextNode = newNode;
              }
  
              tail = newNode;
              dataCount++;
              return true;
          }catch (Exception ex){
              return false;
          }
      }
  
      @Override
      public Object first() {
          try {
              if (head == null) {
                  return null;
              }
  
              cur = head;
              return cur.data;
          }catch (Exception ex){
              return null;
          }
      }
  
      @Override
      public Object next() {
          try{
              if (head == null){
                  return null;
              }
  
              if (cur.nextNode == null){
                  System.out.println("마지막 노드입니다.");
                  return null;
              }
  
              cur = cur.nextNode;
              return cur.data;
          }catch (Exception ex) {
              return null;
          }
      }
  
      @Override
      public Object remove() {
          try{
              if (head == null){
                  return null;
              }
  
              Node tmpNode = head;
              while(tmpNode.nextNode != cur){
                  tmpNode = tmpNode.nextNode;
              }
  
              tmpNode.nextNode = cur.nextNode;
              dataCount--;
              return cur;
          }catch (Exception ex){
              return null;
          }
      }
  
      @Override
      public int count() {
          return dataCount;
      }
  }​

• 메인 구현
  데이터 삽입, 삭제 및 조회 기능 테스트
  

  package List.LinkedList.Single;
  
  public class SingleLinkedListMain {
      public static void main(String[] args) {
          SingleLinkedList linkedList = new SingleLinkedList();
  
          // 리스트 초기화
          linkedList.initialize();
  
          // 리스트에 데이터 삽입
          linkedList.insert(1); linkedList.insert(2);
          linkedList.insert(3); linkedList.insert(4);
          linkedList.insert(5); linkedList.insert(6);
  
          // 첫번째 노드로 설정 및 데이터 가져오기
          Object data = linkedList.first();
          System.out.println(data);
          // data가 null이 될 때까지 반복
          while((data = linkedList.next()) != null) {
              System.out.println(data);
          }
  
          // 데이터 삭제
          Object remove = null;
          data = linkedList.first();
          if ((int)data == 4){
              remove = linkedList.remove();
              System.out.println((int)data + "가 삭제되었습니다.");
              remove = null;
          }
          while((data = linkedList.next()) != null){
              if ((int)data == 4){
                  remove = linkedList.remove();
                  System.out.println((int)data + "가 삭제되었습니다.");
                  remove = null;
              }
          }
  
          // 첫번째 노드로 설정 및 데이터 가져오기
          data = linkedList.first();
          System.out.println(data);
          // data가 null이 될 때까지 반복
          while((data = linkedList.next()) != null) {
              System.out.println(data);
          }
      }
  }​

더미노드를 이용한 단순 연결 리스트

• 기존 연결 리스트에서는 head가 첫 번째 노드를 가리키고 있음
  

  

  
  Dummy Node 이용 시 head가 더미 노드를 가리키고 있음
  

  

• 노드들을 추가/삭제 및 조회 시 첫 번째 노드와 두 번째 이후의 노드간 차이가 있음
   - 첫번째 노드를 먼저 가져와서 처리한 후 next 메소드로 다음 노드를 참조하는 방식
  

          // 데이터 삭제
          Object remove = null;
          data = linkedList.first();
          if ((int)data == 4){
              remove = linkedList.remove();
              System.out.println((int)data + "가 삭제되었습니다.");
              remove = null;
          }
          while((data = linkedList.next()) != null){
              if ((int)data == 4){
                  remove = linkedList.remove();
                  System.out.println((int)data + "가 삭제되었습니다.");
                  remove = null;
              }
          }​

  
  위와같은 단점을 해결하기 위해 더미 노드를 추가함으로서 추가/삭제 및 조회 시 차이가 없도록 함
  

          Object remove = null;
          linkedList.first();
          while((data = linkedList.next()) != null){
              if ((int)data == 4){
                  remove = linkedList.remove();
                  System.out.println((int)data + "가 삭제되었습니다.");
                  remove = null;
              }
          }​

수정된 코드

DummySingleLinkedList.java

package List.LinkedList.Single;
import List.List;

public class DummySingleLinkedList implements List {
    public class Node {
        Object data;
        Node nextNode;

        public Node(Object data, Node nextNode){
            this.data = data;
            this.nextNode = nextNode;
        }

        public Node() {
            this.data = null;
            this.nextNode = null;
        }
    }

    Node head = null;
    Node tail = null;
    Node cur = null;

    Node newNode = null;
    int dataCount = 0;

    @Override
    public void initialize() {
//        head = null;
//        tail = null;
        head = new Node();
        tail = head;
        cur = null;
        newNode = null;
    }

    @Override
    public boolean insert(Object data) {
        try {
            newNode = new Node(data, null);

//            if (head == null) {
//                head = newNode;
//            } else {
//                tail.nextNode = newNode;
//            }

            tail.nextNode = newNode;
            tail = newNode;
            dataCount++;
            return true;
        }catch (Exception ex){
            return false;
        }
    }

    @Override
    public Object first() {
        try {
//            if (head == null) {
//                return null;
//            }

            cur = head;
            return cur.data;
        }catch (Exception ex){
            return null;
        }
    }

    @Override
    public Object next() {
        try{
//            if (head == null){
//                return null;
//            }

            if (cur.nextNode == null){
                System.out.println("마지막 노드입니다.");
                return null;
            }

            cur = cur.nextNode;
            return cur.data;
        }catch (Exception ex) {
            return null;
        }
    }

    @Override
    public Object remove() {
        try{
//            if (head == null){
//                return null;
//            }

            Node tmpNode = head;
            while(tmpNode.nextNode != cur){
                tmpNode = tmpNode.nextNode;
            }

            tmpNode.nextNode = cur.nextNode;
            dataCount--;
            return cur;
        }catch (Exception ex){
            return null;
        }
    }

    @Override
    public int count() {
        return dataCount;
    }
}

DummySingleLinkedListMain.java

package List.LinkedList.Single;

public class DummySingleLinkedListMain {
    public static void main(String[] args) {
        DummySingleLinkedList linkedList = new DummySingleLinkedList();

        // 리스트 초기화
        linkedList.initialize();

        // 리스트에 데이터 삽입
        linkedList.insert(1); linkedList.insert(2);
        linkedList.insert(3); linkedList.insert(4);
        linkedList.insert(5); linkedList.insert(6);

        // 첫번째 노드로 설정
        Object data = null;
        linkedList.first();
        // data가 null이 될 때까지 반복
        while((data = linkedList.next()) != null) {
            System.out.println(data);
        }

        // 데이터 삭제
        Object remove = null;
        linkedList.first();
        while((data = linkedList.next()) != null){
            if ((int)data == 4){
                remove = linkedList.remove();
                System.out.println((int)data + "가 삭제되었습니다.");
                remove = null;
            }
        }

        // 첫번째 노드로 설정
        linkedList.first();
        // data가 null이 될 때까지 반복
        while((data = linkedList.next()) != null) {
            System.out.println(data);
        }
    }
}

결과

순차 리스트

순차 리스트

• 데이터가 메모리에 연속적으로 저장됨 (ex. 배열 등)
• 장점
  1) 인덱스로 데이터에 접근할 수 있으므로 속도가 빠름
• 단점
  1) 배열의 길이가 사전에 정의되어야 함
  2) 중간 데이터 삭제 시 해당 인덱스 이후의 값들은 한 칸씩 이동이 발생

설명

• 삽입
  - 보통 배열의 마지막에 데이터가 삽입되며, 삽입 시 배열의 크기도 고려해야 함
  - 배열의 중간에 데이터를 삽입하기 위해서는 배열의 길이가 충분한지 확인해야 하며, 삽입된 위치 뒤에 존재하는 모든 데이터들이 한 칸씩 뒤로 이동해야 하므로 중간에 데이터 삽입 시 비효율적
  - 시간 복잡도 : O(n)
  
  
• 삭제
  - 배열의 중간에 위치한 데이터를 삭제할 경우 해당 위치의 뒤 데이터들은 한 칸씩 앞으로 이동해야 하므로 배열의 크기가 크고 삭제가 빈번할수록 비효율적
  - 시간복잡도 : O(n)
  
  
• 조회(검색)
  - 배열에 존재하는 데이터에 대한 인덱스 값들이 고정되어 있기 때문에 조회가 간편함
  - 시간복잡도 : O(n) [찾으려는 값이 없을 경우]
  
  
• 접근
  - 배열의 인덱스로 데이터에 바로 접근할 수 있음
  - 시간복잡도 : O(1)
  
  

추상 자료형 (ADT)

구현

• 디렉토리 구조
  

  

• 인터페이스 구현
  다형성을 위해 List관련 메소드를 인터페이스로 구현

  package List;
  
  // 다형성을 위해 List를 인터페이스로 생성
  public interface List {
      // 리스트 초기화
      void initialize();
      // 리스트에 데이터 삽입 (어떤 값이 올 지 모르므로 Object를 인자로 받음)
      boolean insert(Object data);
      // 첫 번째 데이터를 가리키도록 하며 값을 반환
      Object first();
      // 현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
      Object next();
      // 현재 참조하고 있는 데이터를 지움
      Object remove();
      // 리스트에 저장된 데이터의 개수를 반환
      int count();
  }

• 순차 리스트 구현
  실제 리스트 코드 작성
  

  package List.ArrayList;
  import List.List;
  
  public class ArrayList implements List {
      // 리스트 최대 개수를 10으로 지정
      final int MAX_LIST_COUNT = 10;
      Object[] list = new Object[MAX_LIST_COUNT];
      // 현재 위치 저장 변수 (아무것도 참조하고 있지 않으므로 -1)
      int curPosition = -1;
      // 리스트에 저장된 데이터 개수
      int countOfData = 0;
  
      @Override
      public void initialize() {
          curPosition = -1;
          countOfData = 0;
          for(int i=0; i<MAX_LIST_COUNT; i++){
              list[i] = null;
          }
      }
  
      @Override
      public boolean insert(Object data) {
          if (data == null){
              System.out.println("null 값을 추가할 수 없습니다.");
              return false;
          }
  
          if (countOfData >= 100){
              System.out.println("더이상 데이터를 추가할 수 없습니다.");
              return false;
          }
  
          // 리스트에 데이터 저장
          list[countOfData++] = data;
          return true;
      }
  
      @Override
      public Object first() {
          if (countOfData == 0){
              System.out.println("데이터가 없습니다.");
              return null;
          }
  
          // 첫 번째를 가리키도록 설정
          curPosition = 0;
          // 첫 번째 데이터 반환
          return list[curPosition];
      }
  
      @Override
      public Object next() {
          if (curPosition >= countOfData - 1){
              System.out.println("데이터가 없습니다.");
              return null;
          }
  
          curPosition++;
          return list[curPosition];
      }
  
      @Override
      public Object remove() {
          if (countOfData == 0){
              System.out.println("데이터가 없습니다.");
              return null;
          }
  
          // 현재 참조된 데이터를 제거하기 위해 변수에 할당
          Object rData = list[curPosition];
          // 한 칸씩 당기기 위한 반복문
          for(int i=curPosition; i<countOfData - 1; i++){
              list[i] = list[i+1];
          }
  
          // 데이터가 제거됐으므로 개수와 위치를 하나씩 감소
          countOfData--;
          curPosition--;
          return rData;
      }
  
      @Override
      public int count() {
          return countOfData;
      }
  }

  
  
• 메인 구현
  데이터 삽입, 삭제 및 조회 기능 테스트
  

  package List.ArrayList;
  
  public class Main {
      public static void main(String[] args) {
          ArrayList list = new ArrayList();
  
          // 리스트 초기화
          list.initialize();
  
          // 리스트 데이터 추가
          list.insert(1); list.insert(2);
          list.insert(3); list.insert(4);
          list.insert(5); list.insert(6);
  
          // 첫 번째 인덱스를 가리키도록 설정
          Object data = list.first();
          System.out.println(data);
          // data가 null이 아닐때까지 반복
          while((data = list.next()) != null){
              System.out.println(data);
          }
  
          // data 삭제
          Object rData = null;
          data = list.first();
          if ((int)data == 4){
              rData = list.remove();
              System.out.println(rData + " 데이터가 삭제되었습니다.");
              rData = null;
          }
          while((data = list.next()) != null){
              if ((int)data == 4){
                  rData = list.remove();
                  System.out.println(rData + " 데이터가 삭제되었습니다.");
                  rData = null;
              }
          }
  
          // 삭제 후 재출력
          data = list.first();
          System.out.println(data);
          // data가 null이 아닐때까지 반복
          while((data = list.next()) != null){
              System.out.println(data);
          }
      }
  }

알고리즘 문제를 풀다가 반복문을 이용해 문자열을 합치는 부분이 있었다. 간단한 문제여서 String으로 문자열을 합쳤었는데 다른 사람들의 풀이를 보니 StringBuilder로 문제를 풀었다. 해당 문제를 String과 StringBuilder로 풀어봤는데 속도 차이가 많이 나서 어떤 차이 때문에 그런지 확인해보려고 한다. 

String

• String은 불변(immutable)한 객체이며, 한 번 생성되면 내용을 변경할 수 없으며 길이가 정해져 있다. 이러한 특성 때문에 멀티스레드 환경에서 사용하기 적절하다. 
  

  public class TEST {
      public static void main(String[] args){
          String str = "ABC";
          System.out.println("ABC : " + str.hashCode());
  
          str = "AAA";
          System.out.println("AAA : " + str.hashCode());
      }
  }​

  

  
  
  위 코드는 동일한 str 변수이지만, ABC와 AAA를 가리키는 참조값이 다른 것을 확인할 수 있다.
• 위 결과에서 알 수 있는 것처럼, 문자열 조작(추가, 자르기 등) 시 새로운 객체를 생성해 조작된 문자열을 할당하고 기존 String 객체는 GC(Garbage Collection)에 의해 수거된다. 
  

  public class TEST {
      public static void main(String[] args){
          String str = "ABC";
          System.out.println("ABC : " + str.hashCode());
  
          str += "AAA";
          System.out.println("ABCAAA : " + str.hashCode());
      }
  }

  

  단, JDK 1.5 이상부터는 위와 같이 + 로 문자열을 합칠 경우 컴파일러 단에서 자동으로 StringBuilder로 변경해준다고 한다. 
  
  
• String 객체는 Comparable 인터페이스를 상속하고 있기 때문에 equals 메서드로 문장이 동일한지 확인 가능하지만 StringBuilder는 Comparable 인터페이스를 상속하지 않기 때문에 equals 메서드가 없으며 비교 메서드가 따로 존재하지 않는다. 
• 새로운 String 객체를 만들고 값을 할당할 때 JVM(Java Virtual Machine)은 내부적으로 가지고 있는 string pool에서 같은 값이 있는지 확인한다. 같은 값이 있을 경우, pool에서 해당 객체의 참조값을 반환하며 값이 없을 경우엔 pool에 값을 생성한 후 참조값을 반환한다. 그래서 각 다른 String 객체에 같은 값을 할당하면 가리키는 값이 동일하며 똑같은 값을 두 번 할당하지 않기 때문에 메모리 또한 절약할 수 있다.
  

  public class TEST {
      public static void main(String[] args){
          String str = "ABC";
          String str2 = "ABC";
          System.out.println("str : " + str.hashCode());
          System.out.println("str2 : " + str2.hashCode());
      }
  }​

  

StringBuilder/StringBuffer

• StringBuilder는 가변(mutable)한 객체이며 내용의 변경이 가능하며, 내용을 변경할 경우 내부에서 내용의 길이를 변경한다. 이러한 특성 때문에 멀티스레드에서 사용하기에는 적절하지 않다. 
  

  public class TEST {
      public static void main(String[] args){
          StringBuilder sb = new StringBuilder("ABC");
          System.out.println(sb.toString() + " : " + sb.hashCode());
  
          sb.delete(0, sb.length());
          sb.append("AAA");
          System.out.println(sb.toString() + " : " + sb.hashCode());
      }
  }​

  
  

  

  동일한 sb 변수에 ABC값을 할당한 후 hashCode값과 sb 변수에 할당되어있는 값을 지우고 append() 메서드로 AAA 값을 할당한 결과 동일한 참조값을 가지고 있음을 볼 수 있다.
  
  
• StringBuilder는 문자열 조작 시 새로운 객체를 할당하지 않으며 단순히 내부에서 문자열의 길이를 변경해 사용한다. 
  

  public class TEST {
      public static void main(String[] args){
          StringBuilder sb = new StringBuilder("ABC");
          System.out.println(sb.toString() + " : " + sb.hashCode());
  
          sb.append("AAA");
          System.out.println(sb.toString() + " : " + sb.hashCode());
      }
  }​

  
  

  

• String에서 언급했지만 StringBuilder는 Comparable 인터페이스를 상속하지 않기 때문에 equals 메서드를 이용한 비교가 불가능하다. 따라서 아래와 같이 String 형식으로 변환 후 비교를 진행해야 한다.
  

  public class TEST {
      public static void main(String[] args){
          StringBuilder sb = new StringBuilder("ABC");
          StringBuilder sb2 = new StringBuilder("ABC");
  
          if (sb.toString().equals(sb2.toString())){
              System.out.println("sb, sb2 is equal");
          }
          else{
              System.out.println("sb, sb2 is not equal");
          }
      }
  }​

  

• String과 다르게 StringBuilder는 객체에 동일한 값을 할당하더라도 참조값이 서로 다름을 확인할 수 있다.
  

  public class TEST {
      public static void main(String[] args){
          StringBuilder sb = new StringBuilder("ABC");
          System.out.println("sb : " + sb.hashCode());
  
          StringBuilder sb2 = new StringBuilder("ABC");
          System.out.println("sb2 : " + sb2.hashCode());
      }
  }​

  
  

  

   
• StringBuffer는 StringBuilder와 사용하는 메서드가 같은데, 차이점이라면 synchronized 키워드가 존재하여 멀티스레드 환경에서 안전하다고 한다. 

String vs StringBuilder/StringBuffer 성능 비교

동일한 문자를 100만 번 반복했을 때의 속도를 비교해보자.

public class TEST {

    private static final int REPEAT_COUNT = 1000000;

    public static void main(String[] args){
        long start, end;

        start = System.currentTimeMillis();
        StringAppend();
        end = System.currentTimeMillis();
        System.out.println("StringAppend : " + (end - start) + "ms");

        start = System.currentTimeMillis();
        StringBuilderAppend();
        end = System.currentTimeMillis();
        System.out.println("StringBuilderAppend : " + (end - start) + "ms");

        start = System.currentTimeMillis();
        StringBufferAppend();
        end = System.currentTimeMillis();
        System.out.println("StringBufferAppend : " + (end - start) + "ms");
    }

    public static void StringAppend(){
        String str = "";
        for(int i=0; i<REPEAT_COUNT; i++){
            str += '!';
        }
    }

    public static void StringBuilderAppend(){
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<REPEAT_COUNT; i++){
            sb.append("!");
        }
    }

    public static void StringBufferAppend(){
        StringBuffer sb = new StringBuffer();
        for(int i=0; i<REPEAT_COUNT; i++){
            sb.append("!");
        }
    }
}

결과에서 확실하게 알 수 있듯이 String을 + 문자로 계속 추가하게 되면 객체의 생성, 삭제가 계속해서 발생하게 되며 GC가 개입하기 때문에 단순히 문자열을 연결할 경우 속도면에서 매우 불리하다. 그리고 StringBuffer를 이용한 값이 StringBuilder보다 조금 더 오래 걸리는데, 그 이유가 StringBuffer는 내부적으로 thread-safe 를 유지하기 위해 별도의 작업을 진행하기 때문에 시간차이가 난다고 한다.

https://coderanch.com/t/666742/java/understand-StringBuffer-thread-safe-StringBuilder

위 주소에는 StringBuilder와 StringBuffer를 Thread 환경에서 사용했을 때 어떻게 다른지 알 수 있는 예제코드가 댓글에 달려있다. 

결론

1. 간단한 문자열 조작은 단순히 String 객체를 이용해 +로 조작하는 것이 가독성에 좋다.

2. 빈번한 문자열 조작이 필요할 경우 StringBuilder나 StringBuffer를 이용하는 것이 성능상에 유리하다.

3. 멀티스레드 환경에서 thread-safe 해야한다면 StringBuffer를, 그렇지 않다면 StringBuilder를 이용하는 것이 성능에 유리하다.

정규표현식이란?

• 특정 문자열을 처리할 때 사용하는 방법 중 하나
• 특정 문자열에서 패턴을 검색하거나 치환할 때 사용되며 기존에는 코드로 직접 작성해야 했으나, 이 정규표현식을 이용하면 간단하게 문자열을 처리할 수 있음
  ex) 이메일 주소 및 핸드폰 번호 검증 등
• 입력이 불가능한 문자들이 들어있는지 사전에 확인하여 보안상으로도 유용함
  ex) SQL에서 주석으로 표현되는 ' -- 와 같은 문자 확인

Pattern, Matcher 클래스

• Pattern 클래스
   - 검색 또는 치환할 패턴을 정의(Compile)하는 클래스
• Matcher 클래스
   - 패턴을 해석해서 문자열이 일치하는지 확인하는 클래스

예제

• 이메일 주소 검증
  - 이메일 주소는 대부분 test@test.com 형태로, 아이디 부분은 영문 대/소문자, @는 하나이며 주소에는 .이 하나 이상이 들어간다고 가정했다. 이 정보를 기반으로 패턴을 정의하고 검증하는 과정을 거친다.
    더 자세하게 검증 패턴을 만들기 위해서는 직접 구현하거나 검색을 통해 패턴을 알 수 있다.

import java.util.regex.*;

public class 정규표현식 {
    public static void main(String args[]){
        String strPattern = "[a-zA-Z_0-9]+@[a-zA-Z_0-9-]+[.[a-zA-Z_0-9-]]+";

        Pattern p = Pattern.compile(strPattern);

        String email = "test_01@test.co.kr";

        Matcher m = p.matcher(email);

        System.out.println("이메일 검증 : " + m.matches());
    }
}

• 문자열 치환
   - 문자열에서 패턴을 이용해 특정 문자열을 치환할 수 있다. 아래 예제는 . 이 2번 이상인 경우 . 한번으로 치환하는 코드이다.
  

  import java.util.regex.*;
  
  public class 정규표현식 {
      public static void main(String args[]){
          String strPattern = "\\.{2,}";
          String strTmp = "a.bb..ccc...dd..e.";
          String convTmp = strTmp.replaceAll(strPattern, ".");
          
          System.out.println("문자열 치환 : " + convTmp);
      }
  }​

   Matcher 대신 String에서 제공해주는 replaceAll 메소드를 직접 이용해 패턴을 설정하고 치환할 수 있다.
  

  결과 문자열 치환 : a.bb.ccc.dd.e.