[Think Data Structures] Java LinkedList 클래스 구현 및 분석

MyLinkedList 구현 및 분석

---

Java List 인터페이스를 구현한 MyLinkedList<E>를 작성

public class MyLinkedList<E> implements List<E> {
    ..
}

LinkedList(연결리스트)에 대한 간단한 설명

• 자료구조가 연결되었다 함은 노드(node)라는 객체들이 다른 노드에 대한 참조를 포함한 형태로 저장된 것을 의미한다.
• 연결 리스트에서 각 노드는 리스트의 다음 노드에 대한 참조를 포함한다. (연결 구조의 다른 예로는 트리와 그래프가 있음)
• 이때 노드는 둘 이상의 다른 노드에 대한 참조를 포함한다.

LinkedList를 구현하려면 일단 Node를 구현해야 하는데, MyLinkedList<E> 안에 inner class로 Node를 구현한다.

private class Node{
    public E data;
    public Node next;
    
    public Node(E data){
        this.data = data;
        this.next = null;
    }
    
    public Node(E data, Node next){
        this.data = data;
        this.next = next;
    }
}

indexOf 메서드 구현

@Override
public int indexOf(Object o) {
    Node node = head;
    for(int i=0; i<size; i++){
        if(equals(o, node.data)){
            return i;
        }
        node = node.next;
    }
    return -1;
}
 
private boolean equals(Object target, Object element){
    if(target == null){
        return element == null;
    }else{
        return target.equals(element);
    }
}

indexOf 메서드의 증가 차수는 무엇일까?

indexOf의 반복문마다 상수시간인 equals 메서드를 호출한다.(상수시간)

그리고 indexOf 반복문은 n번 실행된다. 운이 없으면 전체 리스트를 순회할 수도 있기 때문에 실행시간은 리스트의 크기에 비례하여 선형시간을 갖게된다. O(n)

add 메서드 구현 (인자가 2개)

@Override
public void add(int index, E element) {
    if(index == 0){
        head = new Node(element, head);
    }else{
        Node node = getNode(index-1);
        node.next = new Node(element, node.next);
    }
    size++;
}

index가 0이라면 맨 앞에 Node 객체를 추가한다. (특별한 경우)

그렇지 않으면 리스트를 순회하며 index-1 위치에 있는 요소를 가져온다.

private Node getNode(int index){
    if(index < 0 || index >= size){
        throw new IndexOutOfBoundsException();
    }
    Node node = head;
    for(int i=0; i<index; i++){
        node = node.next;
    }
    return node;
}

getNode 메서드는 indexOf 메서드와 유사하므로 선형시간을 갖는다.

add 메서드에서 getNode 메서드 전 후가 모두 상수시간이므로, add 메서드는 선형 O(n)의 시간을 갖는다.

remove 메서드 구현

@Override
public E remove(int index) {
    E element = get(index);
    if(index == 0){
        head = head.next;
    }else{
        Node node = getNode(index-1);
        node.next = node.next.next;
    }
    size--;
    return element;
}

index 변수가 0이면 특별한 경우로 처리한다.

그 외에는 index-1 위치의 노드를 찾아 node.next 객체는 건너뛰고 node.next.next 객체로 직접 연결하도록 코드를 수정한다.

get과 getNode 메서드(선형시간)를 제외하면 상수시간 이므로, remove 메서드는 선형시간을 갖는다. O(2n) -> O(n)

※나머지 구현은 https://github.com/ksh901016/thinkDataStructure/ 에서 확인