[자료구조] 2. Singly LinkedList

Singly LinkedList

• ArrayList와 가장 큰 차이점은 '노드'라는 객체를 이용하여 연결하는 것.
• ArrayList의 경우 최상위 타입인 Object[] 을 사용하여 데이터를 담았다면 LinkedList는 배열을 이용하는 것이 아닌 하나의 객체를 두고 그 안에 데이터와 다른 노드를 가리키는 레퍼런스 데이터로 구성하여 여러 노드를 하나의 체인처럼 연결하는 것이다.

---

Node

• 데이터와 다른 노드를 가리키는 주소데이터를 담을 객체
• LinkedList의 가장 기초적 단위

배열과 LinkedList의 구조 비교

위 그림에서 보면 각각의 레퍼런스 변수는 다음 노드 객체를 가리키고 있다. 이렇게 단방향으로 연결된 리스트를 Singly LinkedList라고 한다. 한 마디로 노드들을 연결시킨 형태가 바로 LinkedList이다.

 

이렇게 연결된 노드들에서 '삽입'을 한다면 링크만 바꿔주면 되기 때문에 매우 편리하며, 반대로 '삭제'를 한다면 삭제할 노드에 연결된 이전 노드에서 링크를 끊고 삭제할 노드의 다음 노드를 연결해주면 된다.

---

Node 구현

먼저 Node 클래스를 구현한다. 구현할 LinkedList와 같은 패키지에서 생성한다.

 

public class Node<E> {
    
    E data;
    Node<E> next;       // 다음 노드 객체를 가리키는 레퍼런스 변수
    
    Node(E data) {
        this.data = data;
        this.next = nul;;
    }
}

 

next가 Reference 변수다. 다음 노드를 가리키는 변수이며 '노드 자체'를 가리키기 때문에 타입 또한 Node<E>로 지정했다.

---

Singly LinkedList 구현

<필수 목록>

• 클래스 및 생성자 구성
• search 메소드 구현
• add 메소드 구현
• get, set, indexOf, contains 구현
• remove 메소드 구현
• size, isEmpty, clear 메소드 구현

 

<부가 목록>

• clone, toArray, sort 메소드 구현

---

Singly LinkedList 클래스 및 생성자 구성

List 인터페이스를 Implements 한다. 그리고 멤버 변수와 생성자를 다음과 같이 만들어준다.

 

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

    private Node<E> head;
    private Node<E> tail;
    private int size;

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

 

head : 리스트의 가장 첫 노드를 가리키는 변수

tail : 리스트의 가장 마지막 노드를 가리키는 변수

size : 리스트에 있는 요소의 개수 (연결된 노드의 개수)

 

---

search 메소드 구현

특정 위치의 데이터를 삽입, 삭제, 검색하기 위해서는 처음 노드부터 next 변수를 통해 특정 위치까지 찾아가야 한다.

 

private Node<E> search(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }

    Node<E> x = head;   // head 가 가리키는 노드부터 시작

    for (int i = 0; i < index; i++) {
        x = x.next;     // x 노드의 다음 노드를 x에 저장
    }

    return x;
}

 

---

add 메소드 구현

add 메소드에는 ArrayList와 마찬가지로 크게 3가지로 분류된다.

 

• 가장 앞부분에 추가 - addFirst(E value)
• 가장 마지막에 추가(기본값) - addLast(E value)
• 특정 위치에 추가 - add(int index, E value)

자바에 내장된 LinkedList에서는 add 역할을 addLast 메소드가 하고 특정 위치에 추가는 add(int index, E value) 메소드, 가장 첫 부분 추가는 addFirst 가 한다.

 

0. addFirst(E value)

 

먼저 기본값인 add 및 addLast를 구현하기 전에 addFirst를 먼저 구현한다. 이유는 addLast를 구현할 때 알 수 있다.

 

연결리스트는 말 그대로 '링크'로 연결된 리스트다. 가장 앞에 추가한다면 다음과 같은 과정을 거친다.

 

데이터를 이동시키는 것이 아니라 새로운 노드를 생성하고 새 노드의 레퍼런스 변수(next)가 head 노드를 가리키도록 해준다. 

 

public void addFirst(E value) {
        
    Node<E> newNode = new Node<>(value);    // 새 노드 생성
    newNode.next = head;
    head = newNode;
    size++;

    /**
     * 다음에 가리킬 노드가 없는 경우( 데이터가 새 노드 밖에 없는 경우)
     * 데이터가 한 개(새 노드)밖에 없으므로 새 노드는 처음 시작 노드이자
     * 마지막 노드다. 즉 tail = head 이다.
     */
    if (head.next == null) {
        tail = head;
    }
}

새 노드를 하나 만들고 새로운 노드가 기존의 head를 가리키도록 한다. head를 새 노드로 바꾸어주고 사이즈를 1 증가시킨다.

그리고 아무런 노드가 없는 상태에서 addFirst를 하게 되면 새로운 노드만이 존재하는 상태이다. 즉 head가 가리키는 다음 노드는 없다. 달리 말하면 새로운 노드는 head이자 tail인 것이므로 변수 tail은 head와 같은 노드를 가리키게 된다.

 

 

1. 기본 삽입 : add(E value) & addLast(E value) 메소드

 

add의 기본 값은 addLast라고 했다. LinkedList API를 보면 add 메소드를 호출하면 add 메소드는 addLast를 호출한다. 즉 구현 자체는 addLast를 중점적으로 구현하면 되는 것이다.

 

 

여기서 addFirst를 먼저 구현한 이유가 나온다. size 가 0일 경우 (아무런 노드가 없는 경우) 결국 처음으로 데이터를 추가하는 것이기 때문에 addFirst를 호출하면 된다.

 

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

public void addLast(E value) {
    Node<E> newNode = new Node<>(value);

    if (size == 0) {
        addFirst(value);
        return;
    }

    /**
     * 마지막 노드와 다음 노드가 새 노드를 가리키도록 하고
     * tail이 가리키는 노드를 새 노드로 바꾼다.
     */
    tail.next = newNode;
    tail = newNode;
    size++;
}

 

3. add(int index, E value)

 

이 부분이 가장 처리할 것이 많다. 넣으려는 위치의 앞 뒤로 링크를 새로 업데이트 해주어야 하기 때문이다. 과정은 다음 그림과 같다.

 

먼저 넣으려는 위치(index = 3)의 노드와 이전의 노드를 찾아야 한다.

 

넣으려는 위치의 이전 노드를 prev_Node라고 하고 넣으려는 위치의 기존 노드를 next_Node라고 할 때,

앞서 만든 search 를 사용하여 넣으려는 위치의 -1 위치의 노드(prev_Node)를 찾아내고 next_Node는 prev_Node.next를 통해 찾는다.

 

그리고 prev_Node의 링크를 새로 추가하려는 노드로 변경하고 새로 추가하려고 하는 노드의 링크는 next_Node로 변경해준다.

이때 인덱스는 잘못된 위치를 참조할 가능성을 고려하여 예외처리로 IndexOutOfBoundsException을 한다.

 

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

    if (index == 0) {
        addFirst(value);
        return;
    }

    if (index == size) {
        addLast(value);
        return;
    }

    Node<E> prev_Node = search(index - 1);
    Node<E> next_Node = prev_Node.next;
    Node<E> newNode = new Node<>(value);

    /**
     * 이전 노드가 가리키는 노드를 끊고
     * 새 노드로 변경한다.
     * 또한 새 노드가 가리키는 노드는 next_Node 로 변경한다.
     */
    prev_Node.next = null;
    prev_Node.next = newNode;
    newNode.next = next_Node;
    size++;
}

 

---

remove 메소드 구현

 

remove 메소드 또한 3가지로 나눌 수 있다.

 

• 가장 앞의 요소(head) 삭제 - remove()
• 특정 index의 요소 삭제 - remove(int index)
• 특정 요소를 삭제 - remove(Object value)

삭제연산의 가장 기초는 remove() 메소드로 head가 가리키는 요소, 첫 번째 요소를 삭제하는 것. 인덱스로 생각한다면 0 위치에 있는 요소를 말한다.

 

 

1. remove() 메소드

 

가장 앞에 있는 요소를 제거하는 것. 과정은 다음 그림과 같다.

 

head가 가리키는 노드의 링크와 데이터를 null 로 지워주고 head를 다음 노드로 업데이트를 해준다.

삭제하려는 노드가 리스트에서 유일한 노드였을 경우 해당 노드를 삭제하면 tail이 가리키는 노드 또한 없어지게 된다.

이에 대해서도 정확히 처리한다.

 

public E remove() {
    Node<E> headNode = head;

    if (headNode == null) throw new NoSuchElementException();

    E element = headNode.data;

    Node<E> nextNode = head.next;

    head.data = null;
    head.next = null;

    head = nextNode;
    size--;

    /**
     * 삭제된 요소가 리스트의 유일한 요소일 경우
     * 그 요소는 head 이자 tail 이므로
     * 삭제 되면서 tail 도 가리킬 요소가 없기 때문에
     * size 가 0일 경우 tail 도 Null 로 해준다.
     */
    if (size == 0) {
        tail = null;
    }

    return element;
}

 

 

2. remove(int index) 메소드

 

remove(int index) 메소드는 사용자가 원하는 특정 위치의 요소를 찾아서 삭제하는 것.

삭제하려는 노드를 A노드라고 한다면 A의 이전 노드의 next 변수를 A노드의 다음 노드로 가리키도록 하면 된다.

 

마찬가지로 인덱스 범위를 확인하자.

 

@Override
public E remove(int index) {

    if (index == 0) {
        return remove();
    }

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

    Node<E> prevNode = search(index - 1);
    Node<E> removeNode = prevNode.next;
    Node<E> nextNode = removeNode.next;

    E element = removeNode.data;

    prevNode.next = nextNode;

    if (prevNode.next == null) {
        tail = prevNode;
    }

    removeNode.next = null;
    removeNode.data = null;
    size--;

    return element;
}

 

 

3. remove(Object value) 메소드

 

사용자가 원하는 특정 요소를 리스트에서 찾아서 삭제하는 것.

 

remove(int index)와 동일한 매커니즘으로 작동하지만 고려해야 할 것은 삭제하려는 요소가 존재하는지 부터가 먼저다. 삭제하려는 요소를 찾지 못했다면 false, 찾았다면 remove(int index)와 동일한 삭제 방식을 사용.

 

@Override
public boolean remove(Object value) {
    Node<E> prevNode = head;
    boolean hasValue = false;
    Node<E> x = head;   // removeNode

    // value 와 일치하는 노드를 찾는다. 
    for (; x != null; x = x.next) {
        if (value.equals(x.data)) {
            hasValue = true;
            break;
        }
        prevNode = x;
    }

    // 일치하는 요소가 없을 경우 false 반환
    if (x == null) {
        return false;
    }

    // 삭제하려는 노드가 head 라면 기존 remove 사용
    if (x.equals(head)) {
        remove();
        return true;
    } else {
        // 이전 노드의 링크를 삭제하려는 노드의 다음 노드로 연결
        prevNode.next = x.next;

        // 만약 삭제했던 도느가 마지막 노드라면 tail 을 prevNode 로 갱신
        if (prevNode.next == null) {
            tail = prevNode;
        }

        x.data = null;
        x.next = null;
        size--;

        return true;
    }
}

 

---

get, set, indexOf, contains 메소드 구현

 

1. get(int index) 메소드

 

search 메소드를 이용하면 된다.

 

@Override
public E get(int index) {
    return search(index).data;
}

 

2. set(int index, E value) 메소드

 

set 메소드는 index에 위치한 데이터를 새로운 데이터로 교체하는 것이다.

search를 통해 노드를 찾고, 해당 노드의 데이터만 새로운 데이터로 변경한다.

 

@Override
public void set(int index, E value) {
    Node<E> replaceNode = search(index);
    replaceNode.data = value;
}

 

3. indexOf(Object value) 메소드

 

indexOf 메소드는 사용자가 찾고자 하는 요소의 위치를 반환하는 메소드이다.

찾고자 하는 요소가 중복된다면 가장 먼저 마주치는 요소의 인덱스를 반환한다. 실제로 자바의 indexOf도 동일하게 작동한다.

 

찾고자 하는 것이 없다면 -1을 반환한다.

 

마찬가지로 객체를 비교하는 것이기 때문에 동등연산자가 아닌 equals 로 비교한다.

 

@Override
public int indexOf(Object value) {
    int index = 0;

    for (Node<E> x = head; x != null; x = x.next) {
        if (value.equals(x.data)) {
            return index;
        }
        index++;
    }

    return -1;
}

 

4. contains(Object Value) 메소드

 

contains는 사용자가 찾고자 하는 요소가 존재하는지 안하는지를 찾는 것이다.

indexOf 에서 음수가 반환되었다면 요소가 존재하지 않는다는 것을 이용해 메소드를 구현하면 된다.

 

@Override
public boolean contains(Object value) {
    return indexOf(value) >= 0;
}

---

size, isEmpty, clear 메소드 구현

 

1. size() 메소드

 

 

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

 

 

2. isEmpty() 메소드

 

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

 

3. clear() 메소드

 

모든 요소들을 비우는 메소드이다. 객체 자체를 null 하기 보다는 모든 노드를 하나하나 null 해주는 것이 자바의 가비지 컬렉터가 해당 메모리를 쓰지 않는다고 인지하기 때문에 메모리 관리 효율 측면에서 조금이나마 더 좋다.

 

@Override
public void clear() {
    for (Node<E> x = head; x != null; x = x.next) {
        Node<E> nextNode = x.next;
        x.data = null;
        x.next = null;
        x = nextNode;
    }

    head = tail = null;
    size = 0;
}

 

---

<부가 목록>

clone, toArray, sort 메소드 구현

 

리스트 인터페이스에 선언한 메소드는 모두 구현하였다. 부가 목록의 메소드는 있다면 더 좋을 듯한 메소드들이다.

 

 

1. clone() 메소드

 

LinkedList를 새로 복제하고 싶을 때 쓰는 메소드. ArrayList와 마찬가지로 단순히 = 연산자로 객체를 복사하는 것은 '주소'를 복사(얕은 복사)하는 것이기 때문에 새로 복제한 LinkedList에서 값을 조작하면 원래 LinkedList도 영향을 받는다. 그래서 Cloneable 인터페이스를 Implement 하여 복사를 해주어야 한다.

 

@Override
public Object clone() throws CloneNotSupportedException {

    @SuppressWarnings("unchecked")
    SinglyLinkedList<? super E> clone = (SinglyLinkedList<? super E>) super.clone();

    clone.head = null;
    clone.tail = null;
    clone.size = 0;

    for (Node<E> x = head; x != null; x = x.next) {
        clone.addLast(x.data);
    }

    return clone;
}

 

super.clone 까지는 객체는 생성이 되지만 내부의 데이터 복제까지는 이루어지지 않은 얕은 복사가 된다. 그래서 새로 만들어진 객체 내무의 데이터를 새로 설정해준다.

 

 

2. toArray() 메소드

 

ArrayList와 마찬가지로 크게 두 가지가 있다.

하나는 아무런 인자 없이 현재 있는 리스트를 객체배열(Object[])로 반환해주는 Object[] toArray()가 있고

다른 하나는 리스트를 이미 생성된 다른 배열에 복사해주고자 하는 T[] toArray(T[] a) 가 있다.

 

두 가지 방식의 차이점은 1. ArrayList 포스트에서 확인하길 바란다.

 

하지만 2번 같은 경우는 ArrayList 배열 생성 방식과 차이가 있다.

ArrayList는 내부에서 데이터를 Object[] 배열에 담았기 때문에 데이터 복사가 쉬웠지만, LinkedList는 노드를 사용한 연결리스트이기 때문에 노드 자체가 Integer, String과 같은 래퍼 클래스나, 사용자가 만든 클래스 같은 데이터를 가질 수 없다. 한 마디로 노드 데이터 변수가 객체 타입 변수인 것이지 노드 자체가 객체 타입을 갖지 못한다. 그래서 Arrays.copyOf()나 System.arraycopy를 쓰기 어렵다.

 

대안으로 Array 클래스의 newInstance 메소드를 사용하여 구현한다.

 

public Object[] toArray() {
    Object[] array = new Object[size];
    int idx = 0;
    for (Node<E> x = head; x != null; x = x.next){
        array[idx++] = (E) x.data;
    }

    return array;
}

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size) {
        // Arrays.newInstance(컴포넌트 타입, 생성할 크기)
        a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
    }
    int i = 0;
    Object[] result = a;
    for (Node<E> x = head; x != null; x = x.next) {
        result[i++] = x.data;
    }

    return a;
}

 

첫번째 방법은 어려운 방법이 아니니 두번째 방법에 조금 더 집중해보자.

 

이 부분은 제네릭 메소드로, SinglyLinkedList의 E타입과는 다른 제네릭이다. 예를 들어 E Type이 Integer이고 T 타입은 Object라고 가정해보자.

 

Object는 Integer보다 상위 타입으로 Object 안에 Integer 타입의 데이터를 담을 수 있다. 이 외에도 사용자가 만든 부모, 자식 클래스 같이 상속관계에 있는 클래스들에서 하위 타입이 상위 타입으로 데이터를 받고 싶을 때 쓸 수 있도록 하기 위함이다.

즉, 상위타입으로 들어오는 객체에 대해서도 데이터를 담을 수 있도록 별도의 제네릭 메소드를 구성하는 것. 하위 타입, 즉 축소할 경우 Array 클래스에서 예외를 던지기 때문에 이에 대한 별다른 예외 처리는 필요 없다.

 

그리고 크게 두가지 경우의 수가 있는데 파라미터로 주어지는 배열 a가 현재 리스트의 요소보다 작은 경우, 큰 경우이다.

 

작은 경우에는 size에 맞게 a의 공간을 재할당하면서 리스트에 있던 모든 요소를 복사한다.

LinkedList의 요소가 4개 있다고 가정해보자. 그리고 Object[] copy = new Object[1] 이라는 배열을 하나 만들었는데 공간이 하나이다.

그러면 리스트의 요소 1개만 복사하는 것이 아닌 copy 배열의 사이즈가 4로 증가하여 copy 배열에 LinkedList의 4개의 요소값이 모두 담기는 것이다.

또한 a의 타입을 알기 위해 getClass().getComponentType()을 통해 어떤 유형의 배열인지 파라미터를 넣고 size를 넣어 배열의 크기를 설정한다. 그 다음부터는 얕은 복사를 통해 배열을 만들고 데이터를 넣어주고 a를 반환한다.

반대로 파라미터로 들어오는 배열의 크기가 현재 List보다 크다면 앞 부분부터 a배열에 넣고 반환하면 된다.

 

 

 

3. sort() 메소드

 

ArrayList에서는 내부에서 Object[] 배열을 사용하고 있기 때문에 Arrays.sort를 하면 되기 때문에 구현하지 않았다.

 

하지만 LinkedList 같은 객체로 연결된 리스트들은 다른 방법으로 정렬해야 한다. 객체 배열의 경우 Collections.sort()를 사용하는데 이 또한 내부적으로 Arrays.sort()를 사용한다. 해당 리스트를 Object[]로 변환시키고 Arrays.sort()를 통해 정렬하고 정렬된 데이터를 리스트의 노드에 세팅하는 식이다.

 

만약 Wrapper(Integer, Character, Double)이라면 따로 Comparator를 구현하지 않아도 되지만 사용자 클래스(ex : Student 클래스)를 만든다면 따로 해당 객체에 Comparable를 구현하거나 Comparator를 구현해서 파라미터로 넘겨야 한다.

 

즉 두 가지를 고려해볼 수 있다. 첫 번째는 Comparable 구현이 되어 있어 따로 파라미터로 Comparator를 넘겨주지 않는 경우, 두 번째는 Comparator를 넘겨서 정의된 정렬 방식을 사용하는 경우이다.

 

 

public void sort() {
    /**
     * Comparator 를 넘겨주지 않는 경우 해당 객체의 Comparable 에 구현된 정렬 방식을 사용한다.
     * 만약 구현되어 있지 않다면 cannot be cast to class java.lang.Comparable 에러가 발생.
     * 만약 구현되어 있다면 null 로 파라미터를 넘기면
     * Arrays.sort() 가 객체의 compareTo 메소드에 정의된 방식대로 정렬한다.
     */
    sort(null);
}

@SuppressWarnings({"unchecked", "rawtypes"})
public void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);

    int i = 0;
    for (Node<E> x = head; x != null; x = x.next, i++) {
        x.data = (E) a[i];
    }
}

 

위 코드를 보면 어떤 형태로든 결국 sort(Comparator<? super E> c) 로 간다. 그 다음 Object[] 배열로 toArray()를 통해 Object 배열을 하나 만들고 Arrays.sort를 통해 정렬한다.

실제로도 Collections.sort가 이런식으로 구현이 되어있다.

 

 

Collections.sort() - Comparator 파라미터가 없는 경우 

 

 

 

Collections.sort() - Comparator 파라미터가 주어지는 경우

 

 

그리고 두 메소드 모두 List 인터페이스의 default 메소드인 sort() 메소드로 보낸다.

 

 

List.sort()

 

 

차이점이 있다면 Iterator를 구현하지 않아 예제의 코드는 반복문을 통해 현재 클래스의 노드 데이터를 직접 바꾼다는 것이다.

 

---

Student 클래스를 통해 이름과 성적을 입력 받고 이를 정렬하는 테스트를 해보겠다.

 

<Student가 Comparable을 구현하지 않은 경우>

 

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<Student> studentList = new SinglyLinkedList<>();

        studentList.add(new Student("홍", 92));
        studentList.add(new Student("김", 70));
        studentList.add(new Student("서", 55));
        studentList.add(new Student("박", 88));

        studentList.sort();

        for (int i = 0; i < studentList.size(); i++) {
            System.out.println(studentList.get(i));
        }
    }

    static class Student {
        String name;
        int score;

        public Student(String name, int score) {
            this.name = name;
            this.score = score;
        }

        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", score=" + score +
                    '}';
        }
    }
}

 

Comparable을 구현하지 않아서 해당 객체의 정렬 방법을 모르기 때문에 ClassCastException이 발생하게 된다. 그래서 명시적으로 Array.sort()에 정렬 방식을 구현하던지, Student 클래스에 구현해야한다.

 

 

 

<Comparator의 구현을 통해 Array.sort()에 파라미터를 넘기는 방법>

 

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<Student> studentList = new SinglyLinkedList<>();

        studentList.add(new Student("홍", 92));
        studentList.add(new Student("김", 70));
        studentList.add(new Student("서", 55));
        studentList.add(new Student("박", 88));

        studentList.sort(studentComp);  // studentComp (Comparator)를 파라미터로 넘겨준다.

        for (int i = 0; i < studentList.size(); i++) {
            System.out.println(studentList.get(i));
        }
    }
    
    static Comparator<Student> studentComp = new Comparator<Student>() {
        @Override
        public int compare(Student o1, Student o2) {
            return o2.score - o1.score;
        }
    };

    static class Student {
        String name;
        int score;

        public Student(String name, int score) {
            this.name = name;
            this.score = score;
        }

        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", score=" + score +
                    '}';
        }
    }
}

 

 

 

<Comparable의 구현을 통해 객체의 정렬 방법을 설정하는 방법>

 

클래스에 Comparable을 구현하는 방법이다.

 

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<Student> studentList = new SinglyLinkedList<>();

        studentList.add(new Student("홍", 92));
        studentList.add(new Student("김", 70));
        studentList.add(new Student("서", 55));
        studentList.add(new Student("박", 88));

        studentList.sort();

        for (int i = 0; i < studentList.size(); i++) {
            System.out.println(studentList.get(i));
        }
    }

    static class Student implements Comparable<Student>{
        String name;
        int score;

        public Student(String name, int score) {
            this.name = name;
            this.score = score;
        }

        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", score=" + score +
                    '}';
        }

        @Override
        public int compareTo(Student o) {
            return o.score - this.score;
        }
    }
}

 

---

정리

 

Singly LinkedList에 대한 기본적인 메소드들을 구현해보았다. 자바에서 제공하고 있는 연결리스트는 양방향 리스트이다. 단일 리스트에 비해 고려해야할 것이 더욱 많고 기본적인 구조 이해 없이는 쉽지 않다.

 

ArrayList에 비해 삽입, 삭제 과정에서 '링크'만 끊고 연결만 하면 되기 때문에 편리하지만 검색 과정에서는 head 부터 연결되어 관리되기 때문에 성능이 조금은 떨어진다.

 

그렇기 때문에 삽입, 삭제가 빈번하다면 LinkedList, 데이터 접근이 더 빈번하다면 ArrayList가 더 좋다.

 

 

---

아래의 블로그를 거의 따라하는 식이긴 하지만 자료구조에 대한 이해를 훨씬 더 쉽게 해준 글이다. 수업 따라간다 생각하고 마지막까지 열심히 구현해보려고 한다.

 

참고 : https://st-lab.tistory.com/167