자료구조 스터디 2주차

자료구조-스터디-2주차.md

자바 자료구조 스터디 2주차

이 md 파일은 Typora 에서 작성되었습니다. 읽으실 때, Typora 에서 읽으시는 것이 가장 보기에 좋습니다.

[TOC]

연결 리스트(Linked List) 1

추상 자료형: Abstract Data Type

이 용어를 반드시 알아갑시다.

컴퓨터 공학에서의 추상 자료형(Abstract Data Type; ADT)

ADT라고 불리는 것은 컴퓨터 공학에서 흔히 등장하는 용어, 등장하는 영역에 따라서 실제 의미에서 조금 확장된 개념으로 사용되기 때문에 의미상 차이가 있는 것처럼 느껴질 수 있음.

이 책에서 설명하는 ADT는 자료구조의 관점에서 설명함.

자료구조에서의 추상 자료형

'구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것'

여기서 구조체라는 문법이 등장하는데, Java에선 역시 대응하는게 없습니다.

연산은 연산자를 이용한 기본 연산을 의미하는 것이 아닌, 기능 자체를 의미합니다.(method)

제가 생각하기에 여기서 말하는 ADT에 가까운건 자바의 interface에 가깝다고 생각합니다.

사실 생각해보면, 기능의 명세의 목록정도로 볼 수 있거든요. 거기서 중요한 것은 기능이 어떤 동작을 할 것인지에 대한 약속만 존재하면 되고, 구체적인 구현은 알아서 하면 됩니다.

그리고 이러한 Interface 를 사용하는 자료구조는 Collection Framework에서 아주 잘 알 수 있습니다.

List 인터페이스에 ArrayList, LinkedList 구현체가 있듯이

ADT → ADT의 구현체 구조로 구현하면 될 것 같습니다.

구조체 Wallet의 추상 자료형 정의

"Interface Wallet은 자료구조의 일종이다." 라고 적절히 해석하면 될 것 같습니다. (사실 정확한 표현은 아닙니다.)

"구체적인 기능의 완성과정을 언급하지 않고(추상적), 순수하게 기능이 무엇인지를 나열한 것을 가리켜 '추상 자료형' 또는 간단히 ADT라 한다."

오히려 ADT를 학습하는데 Java의 학습경험이 도움이 많이 되는 것 같습니다.

Wallet의 ADT

Operations:

• int takeOutMoney(int coinNum, int billNum)
  • 해당 지갑에서 돈을 꺼내는 동작
  • 1번째 인자는 꺼낼 동전의 수
  • 2번째 인자는 꺼낼 지폐의 수
  • 반환 값은 꺼내고자 하는 돈의 총액이 반환되고, 지갑에서 돈이 차감됨.
• void putMoney(int coinNum, int billNum)
  • 해당 지갑에 돈을 넣는 동작
  • 1번쨰 인자는 넣을 동전의 수
  • 2번째 인자는 넣을 지폐의 수
  • 반환 값은 없고, 지갑에는 넣을 돈의 총액이 현재 존재하는 금액에 합산됨.

Wallet의 세부 정의는 알 필요가 없습니다. 따라서 interface로 표현할 수 있겠죠?

Wallet.java

public interface Wallet {
  int takeOutMoney(int coinNum, int billNum);
  
  void putMoney(int coinNum, int billNum);
}

JavaDoc까지 작성하면 완벽하겠으나, 시간도 부족하고 해서 생략하겠습니다. ㅠㅠ

여기서 접근 제어자가 왜 없는지 궁금하실 텐데요. Java의 interface를 선언할 때에는 생략 가능합니다. 컴파일러가 알아서 붙여주기 때문이에요.

자료구조의 학습에 ADT의 정의를 포함합니다.

학습 순서

1. 리스트 자료구조의 ADT를 정의한다.(interface를 정의한다.)
2. ADT를 근거로 리스트 자료구조를 활용하는 test code를 작성한다. (우리는 main 메소드에서 확인하는 구닥다리 방법을 쓰지 말자구요!)
3. ADT를 근거로 리스트를 구현한다.

TDD 방식으로 개발하는 것이 되겠죠?

ADT의 본질: ADT를 사용하는 사람에게 사용방법 이외의 불필요한 부분까지 알도록 부담을 주지 않는다.

그 내부 구현을 알지 못해도 활용할 수 있도록 만드는 것이 핵심입니다.

interface 기반 프로그래밍을 하게 되는 것이죠!

배열을 이용한 리스트의 구현

여기서 말하듯이, List는 LinkedList만이 있는 것이 아닌건 다들 아실겁니다.

리스트의 이해

List는 Interface이고, 이를 사용하기 위해서 Java에서는 어떻게하죠?

바로 ArrayList, LinkedList와 같은 구현 클래스를 사용합니다.

그러면 이해가 빠르겠죠? 우리가 사용하는 것은 List의 연산인데, 실제 처리하는 녀석은 ArrayList나 LinkedList죠?

구현 방법의 차이는 사용 방법에 아무런 영향을 미치지 않습니다.

ADT는 표준이 아니기 때문에 다를 수 있음을 알아야 합니다. (예를 들어, 메소드 명이 다르거나, 매개 변수가 다르거나 하는 메소드 시그니처가 다르거나, 아니면 아예 다른 기능을 제공할 수 있겠죠.)

리스트 자료구조의 가장 기본적이고도 중요한 특성 데이터를 나란히 저장하고, 중복된 데이터의 저장을 막지 않습니다.

비교되는 것이 바로 Set(집합)자료구조 인데요, 데이터의 중복저장을 막는다는 것 때문에 알고리즘 문제를 풀 때 많이 사용하곤하죠.

리스트의 ADT

리스트의 ADT를 만들 때에는 데이터의 구체적인 표현을 따라가는 것이 아니라, 추상적인 기능만을 생각해야 합니다.

우리는 Java로 하니까 바로 Interface로 해봅시다. Generics도 활용해봅시다!

List.java

public interface List<E> {
  // 생성자 생략
  
  void insert(E data);
  
  int size();
  
  boolean isEmpty();
  
  boolean contains(Object o);
  
  E get(int index);
  
  E remove(int index);
}

책에서 나온 ADT 중 자바로 구현이 불가능한 것, 그리고 우리가 흔히 쓰는 java의 Collection Framework의 Interface를 참조해서 만든 ADT입니다.

리스트의 ADT를 기반으로 정의된 main 함수

우리는 테스트 코드를 작성할 겁니다.

테스트 코드는 JUnit 5 + AssertJ를 기반으로 작성됩니다.

class ListTest {
  
  @Test
  void ArrayList의_생성_및_초기화() {
    List<Integer> list = new ArrayList<>();
    
    assertThat(list).isNotNull();
  }
  
  @Test
  void 데이터_5개_저장() {
    List<Integer> list = new ArrayList<>();
    list.insert(11);
    list.insert(11);
    list.insert(22);
    list.insert(22);
    list.insert(33);
    
    assertThat(list.size()).isEqualTo(5);
    assertThat(list.get(0)).isEqualTo(11);
    assertThat(list.get(1)).isEqualTo(11);
    assertThat(list.get(2)).isEqualTo(22);
    assertThat(list.get(3)).isEqualTo(22);
    assertThat(list.get(4)).isEqualTo(33);
  }
  
    
  @Test
  void 데이터_5개_저장_후_22인_데이터_모두_삭제() {
    List<Integer> list = new ArrayList<>();
    list.insert(11);
    list.insert(11);
    list.insert(22);
    list.insert(22);
    list.insert(33);
    
    // Iterable을 구현하면 enhanced for loop를 사용할 수 있습니다.
    for (int i = 0; i < list.size(); i++) {
      if (list.get(i) == 22) {
        list.remove(i);
        i--; // 삭제되면 index가 조정되므로 해당 index부터 다시 확인해야 합니다.
      }
    }
    
    assertThat(list.size()).isEqualTo(3);
    assertThat(list.get(0)).isEqualTo(11);
    assertThat(list.get(1)).isEqualTo(11);
    assertThat(list.get(2)).isEqualTo(33);
  }
}

C언어는 복잡한데, Java는 좀 간단하죠? 다 이해할 수 있는 내용이라고 생각합니다.

[문제 03-1]을 테스트 코드로 작성해봅시다.

class Question03_1Test {
  
  @Test
  void 리스트_자료구조_활용() {
    List<Integer> list = new ArrayList<>();
    
    for (int i = 1; i < 10; i++) {
      list.insert(i);
    }
    
    for (int i = 0; i < list.size(); i++) {
      assertThat(list.get(i)).isEqualTo(i + 1);
    }
    
    int actual = 0;
    int expected = 45;
    
    for (int i = 0; i < list.size(); i++) {
      actual += list.get(i);
    }
    
    assertThat(actual).isEqualTo(expected);
    
    for (int i = 0; i < list.size(); i++) {
      int data = list.get(i);
      if (data % 2 == 0 || data % 3 == 0) {
        list.remove(i);
        i--;
      }
    }
    
    // 1, 5, 7
    assertThat(list.size()).isEqualTo(3);
    assertThat(list.get(0)).isEqualTo(1);
    assertThat(list.get(1)).isEqualTo(5);
    assertThat(list.get(2)).isEqualTo(7);
  }
}

리스트! 배열을 기반으로 구현하기

여기서 헤더 파일을 정의하는 부분은 필요한 것만 골라갑시다. 먼저 최초 크기를 100으로 주고 저장된 데이터의 개수를 체크하는 필드와 데이터를 저장할 공간을 마련하면 될 것 같네요.

그리고 나서 implement를 해서 Overriding을 해주면 될 것 같습니다.

ArrayList.java

public class ArrayList<E> implements List<E> {

  private static final int INITIAL_CAPACITY = 100;

  private int size;
  private Object[] arr;

  public ArrayList() {
    this.arr = new Object[INITIAL_CAPACITY];
  }

  @Override
  public void insert(E data) {

  }

  @Override
  public int size() {
    return this.size;
  }

  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public boolean contains(Object o) {
    return false;
  }

  @Override
  public E get(int index) {
    return null;
  }

  @Override
  public E remove(int index) {
    return null;
  }
}

여기서 유의할 점은 Object 배열을 사용했다는 것입니다. 제네릭의 특성은 컴파일 시점에 어떤 타입이 들어올 지 모르기 때문에 위와 같이 처리해줍니다.

초기화시에 size의 값을 따로 지정하지 않는 이유는, 클래스 멤버변수는 객체로 초기화 될 때, default value를 가지기 때문입니다. 단 객체의 경우에는 null로 초기화되니 이점은 유의해야 합니다.

@Override
  public void insert(E data) {
    if (this.size >= INITIAL_CAPACITY) { // 더 이상 저장할 공간이 없다면
      System.out.println("저장이 불가능합니다.");
      return;
    }

    arr[this.size] = data; // 데이터 저장
    this.size++; // 데이터 수의 증가
  }

insert 메소드는 위와같이 구현되면 됩니다. 먼저 크기 체크 후 데이터를 해당 위치에 저장시키는 것이죠.

조회도 인덱스 기반으로 조회하기 때문에 간단히 조회가능합니다,

@Override
public E get(int index) {
  return (E) arr[index];
}

제거도 방법만 이해하면 간단하게 제거 가능합니다.

@Override
public E remove(int index) {
  E data = this.get(index);

  for (int i = index; i < this.size - 1; i++) {
    arr[i] = arr[i + 1];
  }

  this.size--;
  return data;
}

여기서 size - 1인 이유는 마지막 위치 다음 데이터는 존재하지 않기 때문입니다.

contains는 좀 복잡합니다. null 체크 로직이 들어가기 때문입니다.

@Override
public boolean contains(Object o) {
  if (o == null) {
    for (int i = 0; i < this.size; i++) {
      if (this.get(i) == null) {
        return true;
      }
    }
  } else {
    for (int i = 0; i < this.size; i++) {
      if (o.equals(this.get(i))) {
        return true;
      }
    }
  }
  return false;
}

포인터 쪽은 그냥 넘어가면 될 것 같습니다~

배열기반 리스트는 저희는 많이 쓰죠 ^^;

연결 리스트(Linked List) 2

연결 리스트의 개념적인 이해

이번 챕터에서 다루는 것이 Linked List입니다.

Linked! 무엇을 연결하겠다는 뜻인가!

이번 예제코드는 작성하지 않겠습니다. 대신 배열 기반 리스트의 단점만 알아봅시다.

배열 기반 리스트는 메모리의 특성이 정적이어서(길이의 변경이 불가능해서) 메모리의 길이를 변경하는 것이 불가능합니다.

바로 길이 조정이 어려운 점 때문에 우리는 자바를 사용할 때, Array를 사용하는 것이 아니라 ArrayList를 사용해서 크기 조정은 라이브러리가 하도록 맡기죠.

필요한 메모리의 크기에 유동적으로 대응하지 못하기 때문에 Linked List를 생각하게 된 것입니다.

예제는 C언어로 짜여진 코드여서 혹시 해석하기가 어렵다면 제가 짠 코드를 분석해보시기 바랍니다.

LinkedRead.java

import java.util.Scanner;

public class LinkedRead {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    Node<Integer> head = null;
    Node<Integer> tail = null;
    Node<Integer> cur = null;

    Node<Integer> newNode;
    int readData;

    // 데이터를 입력 받는 과정
    while (true) {
      System.out.print("자연수 입력(0은 탈출) : ");
      readData = Integer.parseInt(sc.nextLine()); // 예외처리가 필요하지만 하지 않았습니다.

      if (readData == 0) {
        break;
      }

      newNode = new Node<>(readData);

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

    // 입력 받은 데이터의 출력과정
    System.out.println("\n입력 받은 데이터 전체 출력!");
    if (head == null) {
      System.out.println("저장된 자연수가 존재하지 않습니다.");
    } else {
      cur = head;
      System.out.print(cur.data + " ");

      while (cur.next != null) {
        cur = cur.next;
        System.out.print(cur.data + " ");
      }
    }
    
    // 저장된 데이터를 삭제하는 과정
    if (head != null) {
      Node<Integer> delNode = head;
      Node<Integer> delNextNode = head.next;

      System.out.println(head.data + "을(를) 삭제합니다.");
      head = null; // 참조하는 것이 없어져서 gc의 대상이 됩니다.

      while(delNextNode != null) {
        delNode = delNextNode;
        delNextNode = delNode.next;

        System.out.println(delNode.data + "을(를) 삭제합니다.");
        delNode = null;
      }
      tail = null;
      cur = null;
    }
  }

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

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

결과

자연수 입력(0은 탈출) : 2 자연수 입력(0은 탈출) : 4 자연수 입력(0은 탈출) : 6 자연수 입력(0은 탈출) : 8 자연수 입력(0은 탈출) : 0

입력 받은 데이터 전체 출력! 2 4 6 8

Node가 데이터와 다음 데이터의 위치를 저장할 공간을 가지고 있다는 사실이 중요합니다.

연결리스트의 기본적인 원리는 다음 노드를 저장할 공간을 미리 만들어두고, 필요시에 다음 노드를 연결하는 식으로 메모리를 유동적으로 활용할 수 있는 것입니다.

연결 리스트에서의 데이터 삽입

코드를 보면서 이해하면 쉬울 것 같습니다. ^^

그림을 직접 그려가면서 이해하면 더 쉬워요!

연결 리스트에서의 데이터 조회

삽입을 이해했다면 조회의 원리도 이해하기 쉬우실 겁니다.

cur가 가리키는 Node를 순서대로 읽는다는 것을 파악하시면 됩니다!

연결 리스트에서의 데이터 삭제

사실 자바는 언어 자체에서 메모리 해제를 지원해주기 때문에, 굳이 이런 과정을 거칠 필요는 없습니다.

제거하는 방식이 어떤지만 살펴보시기 바랍니다.

한 데이터를 삭제하고, 이전 데이터와 다음 데이터를 어떻게 이어줄지 고민해보시길 바랍니다.

정리하기: 연결 리스트와 관련해서 어디까지 공부한 것인가?

사실 제가 생각하기에도 이 방식은 별로 도움이 되지 않습니다. 대신 Node를 다루는 방법 하나는 알 수 있다는 점 때문에 예제로 실어둔 것 같습니다.

[문제04-1]은 한 번 각자 풀어보시면 좋을 것 같습니다.

단순 연결 리스트의 ADT와 구현

ADT가 확장됩니다. 따라서 저희의 List 인터페이스도 확장될 필요성이 있겠네요.

List.java

import java.util.Comparator;

public interface List<E> {

  void insert(E data);

  int size();

  boolean isEmpty();

  boolean contains(Object o);

  E get(int index);

  E remove(int index);

  void setSortRule(Comparator<E> comp);
}

그런데 java에서 이런식의 코드를 작성한 적이 없어서 좀 고민이 됩니다. ㅎㅎ..

그래서 ISP를 지키면서 확장임을 명시하기 위해 다음과 같은 인터페이스를 추가로 정의했습니다.

그래서 위의 setSortRule은 제거하게 됩니다.

SortedList.java

import java.util.Comparator;

public interface SortedList<E> extends List<E> {
  void setSortRule(Comparator<E> comp);
}

이 책에서는 머리와 꼬리 둘 중 어느 것을 선택할 것인지 생각하도록 합니다.

책에 내용이 조금 오해할 수 있는게, 리스트는 순서를 가진 자료구조는 맞지만, 저장된 순서를 유지할 필요는 없다는 얘기입니다.

여튼 head 노드에 추가하는 방식으로 한다고 합니다.

함수포인터 얘기가 나오는데, 저희랑은 상관 없는 얘기로 보면 됩니다.

Comparator를 넣어준 이유는, 정렬 관련된 기능을 제공하기 때문입니다.

더미노드를 추가하는 이유는 로직의 일관성(if else 문을 제거)을 위함입니다.

더미노드 기반의 LinkedList Test 코드 작성

SortedListTest.java

package list;

import static org.assertj.core.api.Assertions.assertThat;

import org.junit.jupiter.api.Test;

class SortedListTest {

  @Test
  void SortedList의_생성_및_초기화() {
    SortedList<Integer> list = new DummyLinkedList<>();

    assertThat(list).isNotNull();
  }

  @Test
  void 데이터_5개_저장() {
    SortedList<Integer> list = new DummyLinkedList<>();
    list.insert(11);
    list.insert(11);
    list.insert(22);
    list.insert(22);
    list.insert(33);

    assertThat(list.size()).isEqualTo(5);
    assertThat(list.contains(null)).isFalse();
    assertThat(list.contains(11)).isTrue();
    assertThat(list.contains(22)).isTrue();
    assertThat(list.contains(33)).isTrue();
    assertThat(list.contains(44)).isFalse();
    assertThat(list.get(0)).isEqualTo(33);
    assertThat(list.get(1)).isEqualTo(22);
    assertThat(list.get(2)).isEqualTo(22);
    assertThat(list.get(3)).isEqualTo(11);
    assertThat(list.get(4)).isEqualTo(11);
  }

  @Test
  void 데이터_5개_저장_후_22인_데이터_모두_삭제() {
    SortedList<Integer> list = new DummyLinkedList<>();
    list.insert(11);
    list.insert(11);
    list.insert(22);
    list.insert(22);
    list.insert(33);

    // Iterable을 구현하면 enhanced for loop를 사용할 수 있습니다.
    for (int i = 0; i < list.size(); i++) {
      if (list.get(i) == 22) {
        list.remove(i);
        i--; // 삭제되면 index가 조정되므로 해당 index부터 다시 확인해야 합니다.
      }
    }

    assertThat(list.size()).isEqualTo(3);
    assertThat(list.get(0)).isEqualTo(33);
    assertThat(list.get(1)).isEqualTo(11);
    assertThat(list.get(2)).isEqualTo(11);
  }
}

더미노드 기반의 LinkedList구현

DummyLinkedList.java

import java.util.Comparator;

public class DummyLinkedList<E> implements SortedList<E> {

  private int size;
  private Node<E> head = new Node<>(null);
  private Comparator<E> comp;

  @Override
  public void setSortRule(Comparator<E> comp) {
    this.comp = comp;
  }

  @Override
  public void insert(E data) {

  }

  @Override
  public int size() {
    return this.size;
  }

  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public boolean contains(Object o) {
    return false;
  }

  @Override
  public E get(int index) {
    return null;
  }

  @Override
  public E remove(int index) {
    return null;
  }

  private static class Node<T> {

    private T data;
    private Node<T> next;

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

먼저 위와같이 정의를 해줍니다.

head에 null이 정의되도록 하는 것이 아니라, null 값이 담겨있는 더미노드를 정의하는 것입니다.

insert 기능을 추가합니다.

@Override
public void insert(E data) {
  if (this.comp == null) {
    insertToHead(data);
  } else {
    insertWithSortRule(data);
  }
}

// 인터페이스를 통해 제공되는 메소드가 아님!
private void insertToHead(E data) {
  Node<E> newNode = new Node<>(data);

  newNode.next = this.head.next;
  this.head.next = newNode;

  this.size++;
}

// 인터페이스를 통해 제공되는 메소드가 아님!
private void insertWithSortRule(E data) {

}

여기서 주의깊게 봐야할 점은 private으로 감춘 메소드들입니다.

왜 이렇게 했을까요? public으로 공개하면, 테스트가능한 코드가 되는 것은 맞습니다. 하지만, 단점또한 있습니다. 바로 이 클래스를 작성한 개발자 이외의 사람이 메소드를 직접적으로 사용할 수 있게될 수 있습니다.

선택의 문제라서 저는 private로 감추는 것을 선택했습니다.

더미 노드(Dummy Node) 기반의 단순 연결 리스트 구현2: 데이터 조회

책에서 나온 내용은 제가 구현한 코드로는 설명하기 어렵네요. 요건 Iterable하고 좀 더 관련이 있다고 생각합니다.

저는 get(int index) 기반으로 코드를 작성했기 때문에, 동작 원리만 파악하고 넘어가도록 하겠습니다.

@Override
public E get(int index) {
  Node<E> cur = this.head.next;

  for (int i = 0; i < index; i++) {
    cur = cur.next;
  }

  return cur.data;
}

contains() 의 경우에는 다음과 같이 표현할 수 있습니다.

@Override
public boolean contains(Object o) {
  Node<E> cur = this.head.next;
  if (o == null) {
    while (cur.next != null) {
      if (cur.data == null) {
        return true;
      }
      cur = cur.next;
    }
  } else {
    while (cur.next != null) {
      if (o.equals(cur.data)) {
        return true;
      }
      cur = cur.next;
    }
  }
  return false;
}

더미 노드(Dummy Node) 기반의 단순 연결 리스트 구현3: 노드의 삭제

@Override
public E remove(int index) {
  Node<E> before = this.head;
  Node<E> cur = before.next;

  for (int i = 0; i < index; i++) {
    before = cur;
    cur = cur.next;
  }
  before.next = cur.next;
  this.size--;

  return cur.data;
}

before를 두는 기법이 중요합니다.

나머지는 이전과 같네요.

더미 노드(Dummy Node) 기반의 단순 연결 리스트 구현4: 하나로 묶기

DummyLinkedList.java

import java.util.Comparator;

public class DummyLinkedList<E> implements SortedList<E> {

  private int size;
  private Node<E> head = new Node<>(null);
  private Comparator<E> comp;

  @Override
  public void setSortRule(Comparator<E> comp) {
    this.comp = comp;
  }

  @Override
  public void insert(E data) {
    if (this.comp == null) {
      insertToHead(data);
    } else {
      insertWithSortRule(data);
    }
  }

  // 인터페이스를 통해 제공되는 메소드가 아님!
  private void insertToHead(E data) {
    Node<E> newNode = new Node<>(data);

    newNode.next = this.head.next;
    this.head.next = newNode;

    this.size++;
  }

  // 인터페이스를 통해 제공되는 메소드가 아님!
  private void insertWithSortRule(E data) {

  }

  @Override
  public int size() {
    return this.size;
  }

  @Override
  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public boolean contains(Object o) {
    Node<E> cur = this.head.next;
    if (o == null) {
      while (cur.next != null) {
        if (cur.data == null) {
          return true;
        }
        cur = cur.next;
      }
    } else {
      while (cur.next != null) {
        if (o.equals(cur.data)) {
          return true;
        }
        cur = cur.next;
      }
    }
    return false;
  }

  @Override
  public E get(int index) {
    Node<E> cur = this.head.next;

    for (int i = 0; i < index; i++) {
      cur = cur.next;
    }

    return cur.data;
  }

  @Override
  public E remove(int index) {
    Node<E> before = this.head;
    Node<E> cur = before.next;

    for (int i = 0; i < index; i++) {
      before = cur;
      cur = cur.next;
    }
    before.next = cur.next;
    this.size--;

    return cur.data;
  }

  private static class Node<T> {

    private T data;
    private Node<T> next;

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

테스트 코드를 꼭 실행시켜보시길 바랍니다.

연결 리스트의 정렬 삽입의 구현

정렬 삽입은 어려운 주제라고 생각됬네요. 보통은 이렇게 코딩을 하진 않으니까요.

테스트 코드 작성

@Test
void 정렬기준_설정_후_데이터_5개_저장_후_22인_데이터_모두_삭제() {
  SortedList<Integer> list = new DummyLinkedList<>();

  list.setSortRule((o1, o2) -> o2 - o1); // 내림차순

  list.insert(11);
  list.insert(22);
  list.insert(11);
  list.insert(22);
  list.insert(33);

  // Iterable을 구현하면 enhanced for loop를 사용할 수 있습니다.
  for (int i = 0; i < list.size(); i++) {
    if (list.get(i) == 22) {
      list.remove(i);
      i--; // 삭제되면 index가 조정되므로 해당 index부터 다시 확인해야 합니다.
    }
  }

  assertThat(list.size()).isEqualTo(3);
  assertThat(list.get(0)).isEqualTo(33);
  assertThat(list.get(1)).isEqualTo(11);
  assertThat(list.get(2)).isEqualTo(11);
}

아주 간단한 규칙입니다.

뒤에 위치한 수로 앞에 위치한 수를 빼는 것이죠. 그렇게 되면 내림차순 정렬이 되게됩니다.

즉, 1 2 3 4 5 순으로 입력하면, head→5→4→3→2→1 순으로 저장됩니다.

입력 순서도 꼬아봅시다.

항상 정해진 규칙대로 저장이 되어야 함을 알 수 있습니다.

여기서 어려운 점은 삽입의 구현 부인데요. 정렬관련 메소드를 사용할 일이 잘 없어서 그랬던 것 같습니다.

정렬 삽입 코드 구현

private void insertWithSortRule(E data) {
  Node<E> newNode = new Node<>(data);
  Node<E> prev = this.head;

  // 두번째 조건의 의미: 입력된 데이터가 정렬 순서상 비교하는 데이터보다 뒤에 위치하는 경
  // head -> 1 -> 2 -> 3 -> 4 일 때, 2가 들어오면 처음에 1과 비교, 1보다 크므로 다음 순서 2와 비교, 같으므로 해당 위치에 삽입.
  while (prev.next != null && comp.compare(data, prev.next.data) > 0) {
    prev = prev.next;
  }

  newNode.next = prev.next;
  prev.next = newNode;

  this.size++;
}

1. 새로운 노드를 생성합니다.

2. 이전 노드를 기억합니다.

3. 다음 노드를 선택하는 절차를 거칩니다.

   1. prev가 마지막 노드가 아니어야 합니다.
   2. 입력된 데이터와 다음 노드의 데이터를 정렬 기준에 따라 비교해서 입력한 데이터가 head로 부터 멀어져야 하는지 판단합니다.

4. 노드를 넣는 과정을 거칩니다. 1→3 일 때, 2를 넣는다면 일단 2의 다음 노드를 이전 노드의 다음 노드로 변경하고, 1의 다음노드를 2로 변경합니다.

5. 사이즈를 필드로 가지고 있으므로 증가시켜줍니다.

개인적으로 이 부분은 코딩을 직접 해보는 것이 생각을 많이 하도록 해줘서 좋은 것 같습니다.

감사합니다.