🛠️ Singly LinkedList 실전 구현 강의 (JAVA)

Singly LinkedList 자료구조

Singly Linkedlist(단일 연결 리스트) 특징으론 다음과 같이 요약이 가능하다.

• 노드(객체)를 연결하여 리스트 처럼 만든 컬렉션 (배열이 아님)
• 데이터의 중간 삽입, 삭제가 빈번할 경우 빠른 성능을 보장한다.
• 하지만 임의의 요소에 대한 접근 성능은 좋지 않다. 
• 특히 Singly Linked List는 단방향 연결 리스트이기 때문에 만일 리스트의 끝 요소를 탐색하려면, 처음(head)부터 끝까지 순회하며 탐색해야 하기 때문에 굉장히 효율이 떨어진다. (이를 개선한 것이 Doubly Linked List)
• 이밖에 데이터의 저장순서가 유지되고 중복을 허용한다.

[JCF] 🧱 LinkedList 구조 & 사용법 - 정복하기

---

Singly LinkedList 실전 구현하기

우선 본 강의에선 Singly LinkedList의 모든 메서드 기능을 구현하지 않는다.

Singly LinkedList는 자료 구조 한계상 탐색 성능이 좋지 못하기 때문에 현업에서 잘 쓰이지 않으며, 실제로 자바의 LinkedList 클래스도 내부에서는 Doubly LinkedList로 구현되어 있다.

다만, Doubly LinkedList의 작동 원리를 알기 위해선 선수 지식으로 Singly LinkedList의 작동 원리 부터 이해해야 나중에 양방향 연결 구조를 이해하기 용이하다. 따라서 Singly LinkedList는 add, remove 그리고 get, set 기능 정도만 구현하여 객체간의 링크드 구조 원리 정도만 파악해볼 것이다.

---

클래스 필드 & 생성자 정의하기

public class MySinglyLinkedList<E> {
    private Node<E> head; // 노드의 첫 부분을 가리키는 포인트
    private Node<E> tail; // 노드의 마지막 부분을 가리키는 포인트

    private int size; // 요소 갯수

    public MySinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
}

• head : 리스트의 가장 첫 노드를 가리키는 포인트로 이용될 변수
• tail : 리스트의 가장 마지막 노드를 가리키는 포인트로 이용될 변수
• size : 리스트에 있는 요소의 개수(연결 된 노드의 개수)

 

head 와 tail 개념이 필요한 이유

그냥 노드만 next로 서로 참조하여 연결하면 되지 head와 tail이라는 개념이 필요한 이유는 가장 처음 요소와 가장 마지막 요소에 대한 링크를 표현하기 위해서이다. 하나의 노드는 다음 노드 정보만 가지고 있기 때문에, 가장 첫번째 노드를 참조하고 있는 포인트를 만들필요가 있고 그것이 head이다. 마지막 노드는 tail 이다.
또한 뒤에서 배울 addLast() 메서드 같은경우 요소를 맨마지막에 추가해줄때 tail이 없다면 add 할때마다 맨마지막 요소가 어디까지인지 알길이 없기 때문에 맨날 노드들을 처음 부터 순회해야 할지도 모른다.

---

노드 클래스 정의하기

LinkedLIst의 경우 ArrayList와 가장 큰 차이점이라 한다면 바로 '노드(Node)'라는 저장소를 이용하여 연결한다는 점이다. 노드는 대단한 건 아니고 그냥 객체 이다. 이 클래스에는 자료를 저장할 Data 라는 필드와 다음 연결 요소의 주소를 저장하는 Next 라는 필드를 가지고 있을 뿐이다.

그리고 이 노드 객체들이 서로 연결된 형태가 Linked List 인 것이다.

전 시간에 구현해본 ArrayList의 경우 오브젝트 배열(Object[])을 사용하여 데이터를 담아두었다면, LinkedList 는 여러 노드 객체들을 내부적인 처리로 체인(chain)처럼 연결한다.

public class MySinglyLinkedList<E> {
    // ...

    // inner static class
    private static class Node<E> {
        private E item; // Node에 담을 데이터
        private Node<E> next; // 다음 Node 객체를 가르키는 래퍼런스

        // 생성자
        Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }
}

여기서 눈여겨 봐야 할 점은 세가지 이다.

1. 왜 클래스 안에다 클래스를 선언하였는가?
2. 왜 private 접근 지시자인가?
3. 왜 static이 붙었는가?

물론 Node 클래스를 MySinglyLinkedList 클래스 밖에서 선언해도 문제는 없다. 다만 Node 클래스는 오로지 MySinglyLinkedList 클래스에서만 이용되며, 다른 클래스에서는 전혀 이용되지 않는다.

이때 내부 클래스로 선언해주면 여러가지 장점을 얻게 되는데, 이에 대해선 내부 클래스의 장점 포스팅을 참고하길 바란다. 그리고 private 접근제어자의 경우 객체가 외부로 노출되면 보안상의 문제가 발생할 수 있기 때문에 오로지 MySinglyLinkedList 메소드로만 제어가 가능하도록 하기위해 설정되었다.

마지막으로 내부 클래스면 내부 클래스지 static으로 선언한 이유는 메모리 폭발(memory leak) 이슈 때문에 그렇다. 이에 대해선 내부 클래스는 static 으로 선언하라 포스팅을 참고하길 바란다.

---

search 구현하기

add와 remove를 구현하기 앞서 따로 내부 메소드 용으로 search()를 구현하고자 한다.

add와 remove를 하기 위해선 우선 추가 / 삭제할 요소 탐색이 우선이 되기 때문에 반복적으로 재사용되어 따로 메소드로 뺏다.

링크드 리스트의 검색의 경우 인덱스가 없기에 랜덤 엑세스를 할 수 없다. 따라서 N개의 노드를 가지고 있는 노드를 검색할 때, 시간복잡도는 O(N) 이 되게된다.

private Node<E> search(int index) {
    // head(처음 위치) 서부터 차례로 index 까지 검색
    Node<E> n = head;
    for (int i = 0; i < index; i++) {
        n = n.next; // next 필드의 값(다음 노드 주소)를 재대입하면서 순차적으로 요소를 탐색
    }

    return n;
}

이때 반복문 범위를 index 까지 탐색이 아닌 index 전까지만 탐색되어야 하는데 i < index , 이유는 노드의 next 필드 자체가 그 다음 노드를 가리키기 때문이다.

---

add 구현하기

자바의 LinkedList 클래스의 add 메서드 종류를 보면 다음과 같이 4가지가 존재한다.

• void addFirst(Object obj) : 첫번째 위치에 요소 추가
• void addLast(Objec obj) : 마지막 위치에 요소 추가
• boolean add(Object obj) : 마지막 위치에 요소 추가 (성공하면 true)
• void add(int index, Object element) : 지정된 위치에 요소 추가

 

addFirst 구현

public void addFirst(E value) {

    // 1. 먼저 가장 앞의 요소를 가져옴
    Node<E> first = head;

    // 2. 새 노드 생성 (이때 데이터와 next 포인트를 준다)
    Node<E> newNode = new Node<>(value, first);

    // 3. 요소가 추가되었으니 size를 늘린다
    size++;

    // 4. 맨앞에 요소가 추가되었으니 head를 업데이트한다
    head = newNode;

    // 5. 만일 최초로 요소가 add 된 것이면 head와 tail이 가리키는 요소는 같게 된다.
    if (first == null) {
        tail = newNode;
    }
}

연결 리스트에 요소가 첫번째에 추가되는 과정을 그림으로 나타내보자면 다음과 같다.

 

1. head의 값(@100 번지 객체)을 first 변수에 백업

 

2. 새 노드를 추가하면서 요소값과 tmp값(@100)를 넣어 초기화 및 다음 요소로 연결

 

3. head를 새 노드를 바라보도록 업데이트 (@100 → @105)

 

만일 최초의 요소를 추가하는 것이라면 head와 tail이 하나의 객체를 바라보도록 설정하는 것을 잊지 말자.

 

1. head가 null 일 경우

 

2. head와 tail이 최초로 추가된 새 노드를 바라보도록 업데이트

 

addLast 구현

public void addLast(E value) {

    // 1. 먼저 가장 뒤의 요소를 가져옴
    Node<E> last = tail;

    // 2. 새 노드 생성 (맨 마지막 요소 추가니까 next 는 null이다)
    Node<E> newNode = new Node<>(value, null);

    // 3. 요소가 추가되었으니 size를 늘린다
    size++;

    // 4. 맨뒤에 요소가 추가되었으니 tail를 업데이트한다
    tail = newNode;

    if (last == null) {
        // 5. 만일 최초로 요소가 add 된 것이면 head와 tail이 가리키는 요소는 같게 된다.
        head = newNode;
    } else {
        // 6. 최초 추가가 아니라면 last 변수(추가 되기 전 마지막이었던 요소)에서 추가된 새 노드를 가리키도록 업데이트
        last.next = newNode;
    }
}

연결 리스트에 요소가 마지막에 추가되는 과정을 그림으로 나타내보자면 다음과 같다.

 

1. last 변수에 현재 마지막 요소(@300)를 백업

 

2. 새 노드를 추가하고 tail을 업데이트

 

3. 요소가 추가되기 이전의 요소(last 변수)에서 next를 업데이트 (null → @400)

 

add 구현

add()의 동작은 addLast() 와 같다. 실제로 LinkedLIst API를 보면 add 메소드를 호출하면 addLast()를 호출한다.

public boolean add(E value) {
    addLast(value);
    return true;
}

 

add 중간 삽입 구현

1. 리스트 중간에 삽입하기 위해선 가장 먼저 인덱스 범위를 체크해야 한다.
2. 인덱스가 처음과 끝이면 위에서 구현한 addFirst, addLast를 재활용하면 된다.
3. 추가하려는 위치를 구하기 위해 위에서 구현한 search 메서드를 이용한다.
4. 이전 노드(prev_node) 와 다음 노드(next_node) 참조값을 변수에 백업하는 것이 포인트이다.
5. prev_node의 next는 new_node에 연결, new_node는 next_node에 연결 시키도록 함으로써 삽입이 완료된다.

public void add(int index, E value) {

    // 1. 인덱스가 0보다 작거나 size 보다 같거나 클 경우 에러
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }

    // 2. 추가하려는 index가 0이면 addFirst 호출
    if (index == 0) {
        addFirst(value);
        return;
    }

    // 3. 추가하려는 index가 size - 1와 같으면 addLast 호출
    if (index == size - 1) {
        addLast(value);
        return;
    }

    // 4. 추가하려는 위치의 이전 노드 얻기
    Node<E> prev_node = search(index - 1);

    // 5. 추가하려는 위치의 다음 노드 얻기
    Node<E> next_node = prev_node.next;

    // 6. 새 노드 생성 (바로 다음 노드와 연결)
    Node<E> newNode = new Node<>(value, next_node);

    // 7. size 증가
    size++;

    // 8. 이전 노드를 새 노드와 연결
    prev_node.next = newNode;
}

만일 index가 1인 위치(@200번지)에 노드를 삽입한다고 가정한다면 add 중간 삽입 과정은 다음과 같다.

 

1. 추가하려는 위치의 이전 노드(prev_node) 와 다음 노드(next_node)를 임시 저장

 

2. 새 노드 생성 (생성하며 다음 노드에 연결)

 

3. 이전 노드의 참조를 추가된 새 노드에 연결 (@200 → @150)

---

remove 구현하기

LinkedList의 remove 메서드에는 다음과 같이 총 5가지가 존재한다.

• Object removeFirst() : 맨 앞 요소를 제거 (제거한 요소는 반환)
• Object remove() : 맨 앞 요소를 제거
• Object removeLast() : 맨 뒤 요소를 제거 
• Object remove(int index) : 인덱스 위치의 요소를 제거
• boolean remove(Object value) : 요소값이 일치하는 위치의 요소를 제거 (중복 요소값이 있을 경우 맨앞의 요소가 제거)

remove 작동원리는 add 메커니즘의 반대로 생각해서 구현해주면 되어 그리 어렵지 않다.

 

removeFirst 구현

public E removeFirst() {

    // 1. 만약 삭제할 요소가 아무것도 없으면 에러
    if (head == null) {
        throw new IndexOutOfBoundsException();
    }

    // 2. 삭제될 첫번째 요소의 데이터를 백업
    E returnValue = head.item;

    // 3. 두번째 노드를 임시 저장
    Node<E> first = head.next;

    // 4. 첫번째 노드의 내부 요소를 모두 삭제
    head.next = null;
    head.item = null;

    // 5. head가 다음 노드를 가리키도록 업데이트
    head = first;

    // 6. 요소가 삭제 되었으니 크기 감소
    size--;

    // 7. 만일 리스트의 유일한 값을 삭제해서 빈 리스트가 될 경우, tail도 null 처리
    if (head == null) {
        tail = null;
    }

    // 8. 마지막으로 삭제된 요소를 반환
    return returnValue;
}

 

1. 반환할 삭제할 첫번째 요소 데이터를 백업한다.

2. 첫째 요소가 삭제가 되면 두번째 요소가 첫째가 되기 때문에 두번째 요소를 변수 first에 저장해서 나중에 다루도록 한다.

 

3. 첫번째 노드의 모든 데이터를 null로 처리한다.

 

4. head의 포인트를 frist 변수에 저장해두었던 두번째 노드(@200)으로 업데이트한다.

5. 아무것도 연결되지 않아 고아가 되버린 노드는 나중에 GC가 수거해 간다.

 

추가적으로 만일 삭제할 요소가 리스트의 유일한 요소라면, 삭제할시 빈 리스트가 되므로 head와 tail을 null이 되도록 업데이트 해준다.

 

remove 구현

LinkedList의 기본 remove() 동작은 add()와 달리 첫째 요소를 처리한다.

public E remove() {
    return removeFirst();
}

 

인덱스로 remove 구현

public E remove(int index) {

    // 1. 인덱스가 0보다 작거나 size 보다 크거나 같은 경우 에러 (size와 같을 경우 빈 공간을 가리키는 거니까)
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }

    // 2. 인덱스가 0이면 removeFirst 메서드 실행하고 리턴
    if (index == 0) {
        return removeFirst();
    }

    // 3. 삭제할 위치의 이전 노드 저장
    Node<E> prev_node = search(index - 1);

    // 4. 삭제할 위치의 노드 저장
    Node<E> del_node = prev_node.next;

    // 5. 삭제할 위치의 다음 노드 저장
    Node<E> next_node = del_node.next;

    // 6. 삭제될 첫번째 요소의 데이터를 백업
    E returnValue = del_node.item;

    // 7. 삭제 노드의 내부 요소를 모두 삭제
    del_node.next = null;
    del_node.item = null;

    // 8. 요소가 삭제 되었으니 크기 감소
    size--;

    // 9. 이전 노드가 다음 노드를 가리키도록 업데이트
    prev_node.next = next_node;

    // 10. 마지막으로 삭제된 요소를 반환
    return returnValue;
}

 

1. 만일 인덱스 1의 요소를 삭제한다고 하면 먼저 삭제할 위치를 탐색한다.

2. search 메서드에서 반환한 노드를 이용하여, 삭제하려는 위치의 이전 노드(prev_node) 와 삭제 노드(del_node) 그리고 다음 노드(next_node) 참조값을 변수 3개에 저장한다.

3. 반환할 데이터를 백업해둔다.

 

4. del_node의 데이터를 모두 삭제한다.

 

5. prev_node의 next 값을 next_node로 재설정한다.

 

값으로 remove 구현

값으로 요소를 remove 하는 로직은 약간 복잡하다. 왜냐하면  search() 메서드를 사용할수 없기 때문에 직접 순회 전략을 구성해야 되기 때문이다. 

public boolean remove(Object value) {

    // 1. 만약 삭제할 요소가 아무것도 없으면 에러
    if (head == null) {
        throw new RuntimeException();
    }

    // 2. 이전 노드, 삭제 노드, 다음 노드를 저장할 변수 선언
    Node<E> prev_node = null;
    Node<E> del_node = null;
    Node<E> next_node = null;

    // 3. 루프 변수 선언
    Node<E> i = head;

    // 4. 노드의 next를 순회하면서 해당 값을 찾는다.
    while (i != null) {
        if (Objects.equals(i.item, value)) {
            // 노드의 값과 매개변수 값이 같으면 삭제 노드에 요소를 대입하고 break
            del_node = i;
            break;
        }

        // Singly Linked List에는 prev 정보가 없기 때문에 이전 노드에도 요소를 일일히 대입하여야 함
        prev_node = i;

        i = i.next;
    }

    // 5. 만일 찾은 요소가 없다면 리턴
    if (del_node == null) {
        return false;
    }

    // 6. 만약 삭제하려는 노드가 head라면, 첫번째 요소를 삭제하는 것이니 removeFirst()를 사용
    if (del_node == head) {
        removeFirst();
        return true;
    }

    // 7. 다음 노드에 삭제 노드 next의 요소를 대입
    next_node = del_node.next;

    // 8. 삭제 요소 데이터 모두 제거
    del_node.next = null;
    del_node.item = null;

    // 9. 요소가 삭제 되었으니 크기 감소
    size--;

    // 10. 이전 노드가 다음 노드를 참조하도록 업데이트
    prev_node.next = next_node;

    return true;
}

 

removeLast 구현

위에서 구현한 remove(int index) 메서드를 재활용하여 구현한다. 따라서 탐색 시간이 소요되기 때문에 removeFirst() 보다는 O(N) 의 시간이 걸리게 된다.

addLast() 와 같이 tail 을 이용해서 상수 시간안으로 처리되도록 구현 할법 하지만, Singly Linked List는 노드 prev 개념이 없기 때문에 삭제될 노드의 이전 요소를 참조할 방법이 없어, 결국은 처음 부터 끝까지 순회해야 한다는 단점이 존재한다.

public E removeLast() {
    return remove(size - 1);
}

---

get 구현하기

위에서 구현한 search 메서드로 노드를 검색하여 값을 반환하면 된다.

public E get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }

    return search(index).item;
}

---

set 구현하기

public void set(int index, E value) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }

    // 1. search 메소드를 이용해 교체할 노드를 얻는다.
    Node<E> replace_node = search(index);

    // 2. 교체할 노드의 요소를 변경한다.
    replace_node.item = null;
    replace_node.item = value;
}

---

toString 구현하기

마지막으로 링크드 리스트 요소들을 출력하기 위해 Object 클래스의 toString() 메소드를 오버라이딩 하자.

연결 리스트 출력은 어렵게 생각할 필요 없이, 배열을 만들고 각 배열 인덱스 마다 리스트의 노드 요소값을 대입해 복사를 한뒤 문자열로 만들어 반환해주면 된다.

@Override
public String toString() {
    // 1. 만일 head 가 null 일 경우 빈 배열
    if(head == null) {
        return "[]";
    }

    // 2. 현재 size만큼 배열 생성
    Object[] array = new Object[size];

    // 3. 노드 next를 순회하면서 배열에 노드값을 저장
    int index = 0;
    Node<E> n = head;
    while (n != null) {
        array[index] = (E) n.item;
        index++;
        n = n.next;
    }

    // 3. 배열을 스트링화하여 반환
    return Arrays.toString(array);
}

아니면 다음과 같이 직접 문자열 더하기 연산으로도 구현해도 문제는 없다.

@Override
public String toString() {
    if(head == null) {
        return "[]";
    }

    Node<E> n = head;
    String result = "[";

    while(n.next != null) {
        result += n.item + ", ";
        n = n.next;
    }

    // n이 마지막일 경우 n.next가 null이니 루프문을 빠져나오게 되서 마지막 노드 삽입 처리를 해주어야 한다.
    result += n.item + "]"; 

    return result;
}

---

LinkedList 구현 전체 코드

직접 자신이 구현한 자료 구조 알고리즘이 문제없이 동작하는지 메인 메서드에서 테스트하는 것을 잊지말자.

public class MySinglyLinkedList<E> {
    private Node<E> head; // 노드의 첫 부분을 가리키는 포인트
    private Node<E> tail; // 노드의 마지막 부분을 가리키는 포인트

    private int size; // 요소 갯수

    public MySinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    // inner static class
    private static class Node<E> {
        private E item; // Node에 담을 데이터
        private Node<E> next; // 다음 Node 객체를 가르키는 래퍼런스

        // 생성자
        Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }

    private Node<E> search(int index) {
        // head(처음 위치) 서부터 차례로 index 까지 검색
        Node<E> n = head;
        for (int i = 0; i < index; i++) {
            n = n.next; // next 필드의 값(다음 노드 주소)를 재대입하면서 순차적으로 요소를 탐색
        }

        return n;
    }

    public void addFirst(E value) {

        // 1. 먼저 가장 앞의 요소를 가져옴
        Node<E> first = head;

        // 2. 새 노드 생성 (이때 데이터와 next 포인트를 준다)
        Node<E> newNode = new Node<>(value, first);

        // 3. 요소가 추가되었으니 size를 늘린다
        size++;

        // 4. 맨앞에 요소가 추가되었으니 head를 업데이트한다
        head = newNode;

        // 5. 만일 최초로 요소가 add 된 것이면 head와 tail이 가리키는 요소는 같게 된다.
        if (first == null) {
            tail = newNode;
        }
    }

    public void addLast(E value) {

        // 1. 먼저 가장 뒤의 요소를 가져옴
        Node<E> last = tail;

        // 2. 새 노드 생성 (맨 마지막 요소 추가니까 next 는 null이다)
        Node<E> newNode = new Node<>(value, null);

        // 3. 요소가 추가되었으니 size를 늘린다
        size++;

        // 4. 맨뒤에 요소가 추가되었으니 tail를 업데이트한다
        tail = newNode;

        if (last == null) {
            // 5. 만일 최초로 요소가 add 된 것이면 head와 tail이 가리키는 요소는 같게 된다.
            head = newNode;
        } else {
            // 6. 최초 추가가 아니라면 last 변수(추가 되기 전 마지막이었던 요소)에서 추가된 새 노드를 가리키도록 업데이트
            last.next = newNode;
        }
    }

    public void add(int index, E value) {

        // 1. 인덱스가 0보다 작거나 size 보다 같거나 클 경우 에러
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        // 2. 추가하려는 index가 0이면 addFirst 호출
        if (index == 0) {
            addFirst(value);
            return;
        }

        // 3. 추가하려는 index가 size - 1와 같으면 addLast 호출
        if (index == size - 1) {
            addLast(value);
            return;
        }

        // 4. 추가하려는 위치의 이전 노드 얻기
        Node<E> prev_node = search(index - 1);

        // 5. 추가하려는 위치의 다음 노드 얻기
        Node<E> next_node = prev_node.next;

        // 6. 새 노드 생성 (바로 다음 노드와 연결)
        Node<E> newNode = new Node<>(value, next_node);

        // 7. size 증가
        size++;

        // 8. 이전 노드를 새 노드와 연결
        prev_node.next = newNode;
    }


    public boolean add(E value) {
        addLast(value);
        return true;
    }


    @Override
    public String toString() {
        if (head == null) {
            return "[]";
        }

        Node<E> n = head;
        String result = "[";

        while (n.next != null) {
            result += n.item + ", ";
            n = n.next;
        }

        // n이 마지막일 경우 n.next가 null이니 루프문을 빠져나오게 되서 마지막 노드 삽입 처리를 해주어야 한다.
        result += n.item + "]";

        return result;
    }

    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        return search(index).item;
    }

    public void set(int index, E value) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        // 1. search 메소드를 이용해 교체할 노드를 얻는다.
        Node<E> replace_node = search(index);

        // 2. 교체할 노드의 요소를 변경한다.
        replace_node.item = null;
        replace_node.item = value;
    }

    public E removeFirst() {

        // 1. 만약 삭제할 요소가 아무것도 없으면 에러
        if (head == null) {
            throw new RuntimeException();
        }

        // 2. 삭제될 첫번째 요소의 데이터를 백업
        E returnValue = head.item;

        // 3. 두번째 노드를 임시 저장
        Node<E> first = head.next;

        // 4. 첫번째 노드의 내부 요소를 모두 삭제
        head.next = null;
        head.item = null;

        // 5. head가 다음 노드를 가리키도록 업데이트
        head = first;

        // 6. 요소가 삭제 되었으니 크기 감소
        size--;

        // 7. 만일 리스트의 유일한 값을 삭제해서 빈 리스트가 될 경우, tail도 null 처리
        if (head == null) {
            tail = null;
        }

        // 8. 마지막으로 삭제된 요소를 반환
        return returnValue;
    }

    public E remove() {
        return removeFirst();
    }

    public E remove(int index) {

        // 1. 인덱스가 0보다 작거나 size 보다 크거나 같은 경우 에러 (size와 같을 경우 빈 공간을 가리키는 거니까)
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        // 2. 인덱스가 0이면 removeFirst 메서드 실행하고 리턴
        if (index == 0) {
            return removeFirst();
        }

        // 3. 삭제할 위치의 이전 노드 저장
        Node<E> prev_node = search(index - 1);

        // 4. 삭제할 위치의 노드 저장
        Node<E> del_node = prev_node.next;

        // 5. 삭제할 위치의 다음 노드 저장
        Node<E> next_node = del_node.next;

        // 6. 삭제될 첫번째 요소의 데이터를 백업
        E returnValue = del_node.item;

        // 7. 삭제 노드의 내부 요소를 모두 삭제
        del_node.next = null;
        del_node.item = null;

        // 8. 요소가 삭제 되었으니 크기 감소
        size--;

        // 9. 이전 노드가 다음 노드를 가리키도록 업데이트
        prev_node.next = next_node;

        // 10. 마지막으로 삭제된 요소를 반환
        return returnValue;
    }

    public boolean remove(Object value) {

        // 1. 만약 삭제할 요소가 아무것도 없으면 에러
        if (head == null) {
            throw new RuntimeException();
        }

        // 2. 이전 노드, 삭제 노드, 다음 노드를 저장할 변수 선언
        Node<E> prev_node = null;
        Node<E> del_node = null;
        Node<E> next_node = null;

        // 3. 루프 변수 선언
        Node<E> i = head;

        // 4. 노드의 next를 순회하면서 해당 값을 찾는다.
        while (i != null) {
            if (Objects.equals(i.item, value)) {
                // 노드의 값과 매개변수 값이 같으면 삭제 노드에 요소를 대입하고 break
                del_node = i;
                break;
            }

            // Singly Linked List에는 prev 정보가 없기 때문에 이전 노드에도 요소를 일일히 대입하여야 함
            prev_node = i;

            i = i.next;
        }

        // 5. 만일 찾은 요소가 없다면 리턴
        if (del_node == null) {
            return false;
        }

        // 6. 만약 삭제하려는 노드가 head라면, 첫번째 요소를 삭제하는 것이니 removeFirst()를 사용
        if (del_node == head) {
            removeFirst();
            return true;
        }

        // 7. 다음 노드에 삭제 노드 next의 요소를 대입
        next_node = del_node.next;

        // 8. 삭제 요소 데이터 모두 제거
        del_node.next = null;
        del_node.item = null;

        // 9. 요소가 삭제 되었으니 크기 감소
        size--;

        // 10. 이전 노드가 다음 노드를 참조하도록 업데이트
        prev_node.next = next_node;

        return true;
    }

    public E removeLast() {
        return remove(size - 1);
    }
}

public static void main(String[] args) {
    MySinglyLinkedList<Number> l = new MySinglyLinkedList<>();

    l.add(3);
    l.add(6);
    l.add(4);
    l.add(3);
    l.add(8);
    l.add(10);
    l.add(11);
    System.out.println(l); // [3, 6, 4, 3, 8, 10, 11]

    l.add(6, 100);
    l.add(0, 101);
    l.add(1, 102);
    System.out.println(l); // [101, 102, 3, 6, 4, 3, 8, 10, 11, 100]

    l.removeFirst();
    l.removeFirst();
    l.remove(1);
    System.out.println(l); // [3, 4, 3, 8, 10, 11, 100]

    l.remove(new Integer(3));
    l.remove(new Integer(3));
    System.out.println(l); // [4, 8, 10, 11, 100]

    System.out.println(l.get(4)); // 100

    l.set(4, 999);
    System.out.println(l); // [4, 8, 10, 11, 999]
}

---

# 참고자료

https://www.alphacodingskills.com/ds/linked-list.php