LinkedList - 직접 구현하는 연결리스트 3 - 추가와 삭제 2

package collection.link;

public class MyLinkedListV2 {
    private Node first;
    private int size = 0 ;

    public void add(Object e){
        Node newNode = new Node(e);
        if(first == null){
            first = newNode;
        }else{
            Node lastNode = getLastNode();
            lastNode.next=newNode;
        }
        size++;
    }

    public int size() {
        return size;
    }

    private Node getLastNode() {
        Node x = first;
        while(x.next!=null){
            x=x.next;
        }
        return x;
    }

    //추가코드
    public void add(int index, Object e){
        Node newNode = new Node(e);
        if(index ==0){
            newNode.next=first;
            first=newNode;
        }else{
            Node prev = getNode(index - 1);//직전 노드를 찾는것
            newNode.next=prev.next;
            prev.next=newNode;
        }
        size++;
    }

    //추가 코드
    public Object remove(int index){
        Node removeNode = getNode(index);
        Object removedItem = removeNode.item;
        if(index==0){
            first = removeNode.next;
        }else{
            Node prev = getNode(index - 1);
            prev.next=removeNode.next;
        }
        removeNode.item=null;
        removeNode.next=null;
        size--;
        return removedItem;
    }

    public Object set(int index, Object element){
        Node x = getNode(index);
        Object oldValue = x.item;
        x.item = element;

        return oldValue;
    }
    public Object get(int index){
        Node node = getNode(index);
        return node.item;
    }

    private Node getNode(int index) {
        Node x = first;
        for (int i = 0; i < index; i++) {
            x=x.next;
        }
        return x;
    }

    public int indexOf(Object o) {
        int index = 0;
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
        return -1;
    }

    @Override
    public String toString() {
        return "MyLinkedListV1{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }
}

배열리스트와 연결리스트 성능 비교 표

• 배열 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(1)로 빠르게 찾지만, 추가나 삭제 이후에 데이터를 한 칸씩 밀어야 한다. 이 부분이 O(n)으로 오래 걸린다.
• 반면에 연결 리스트는 인덱스를 통해 추가나 삭제할 위치를 O(n)으로 느리게 찾지만, 찾은 이후에는 일부 노드의 참조값만 변경하면 되므로 이 부분이 O(1)로 빠르다.
• 앞에 추가하는 경우 : 연결 리스트는 배열 리스트처럼 추가한 항목의 오른쪽에 있는 데이터를 모두 한 칸씩 밀지 않아도 된다. 단순히 일부 노드의 참조만 변경하면 된다. 따라서 데이터를 앞쪽에 추가하는 경우 보통 연결 리스트가 더 좋은 성능을 제공한다.
  • 배열 리스트 : 데이터를 앞쪽에 추가하는 경우 모든 데이터를 오른쪽으로 한 칸씩 밀어야 한다. O(n)
  • 연결 리스트 : 데이터를 앞쪽에 추가하는 경우 일부 노드의 참조만 변경하면 된다.O(1)

 

마지막에 데이터를 추가하는 경우

• 배열 리스트
  • 인덱스로 마지막 위치를 바로 찾을 수 있다.O(1)
  • 데이터를 마지막에 추가하는 경우 데이터를 이동하지 않아도 된다.O(1)
  • 따라서 O(1)의 성능을 제공한다.
• 연결 리스트
  • 노드를 마지막까지 순회해야 마지막 노드를 찾을 수 있다. 따라서 마지막 노드를 찾는데 O(n)의 시간이 걸린다.
  • 데이터를 추가하는 경우 일부의 참조만 변경하면 된다. O(1)
  • 따라서 O(n)의 성능을 제공한다.

 

배열 리스트 vs 연결 리스트

데이터를 조회할 일이 많고, 뒷 부분에 데이터를 추가한다면 배열 리스트가 보통 더 좋은 성능을 제공한다. 앞쪽의 데이터를 추가하거나 삭제할 일이 많다면 연결 리스트를 사용하는 것이 보통 더 좋은 성능을 제공한다.

 

참고 - 단일 연결 리스트, 이중 연결 리스트

우리가 구현한 연결 리스트는 한 방향으로만 이동하는 단일 연결 리스트다. 노드를 앞뒤로 모두 연결하는 이중 연결 리스트를 사용하면 성능을 더 개선할 수 있다.

뒤에서 설명하지만 자바가 제공하는 연결 리스트는 이중 연결 리스트다. 추가로 자바가 제공하는 연결 리스트는 마지막 노드를 참조하는 변수를 가지고 있어서, 뒤에 추가하거나 삭제하는 경우에도O(1)의 성능을 제공한다. 자세한 내용은 뒤에서 설명한다.