[DS] Array & Linked List

1. Array

가장 기본적인 자료구조로 메모리 상에 같은 타입의 데이터가 연속적으로 저장되어 있다. 이러한 구조는 첫번째 원소의 위치를 기본 index로 offset을 더하여 이어지는 원소들의 위치를 계산하기에 쉽다. 이때문에 array는 논리적 저장순서와 물리적 저장순서가 일치한다. 따라서 index를 통해서 원소에 랜덤하게 접근이 가능하다. 따라서 검색 time complexity 는 O(1) 이다.

 

검색과 달리 삭제와 삽입 등의 과정에서는 해당 원소에 접근하여 작업을 완료한 후 빈 공간에 대해서 다른 원소들을 shifting 해줘야 하는 cost가 발생하고 이 경우의 시간 복잡도는 O(N)이 된다. 그렇기 때문에 array 값의 삽입, 삭제의 Time complexity는 O(N) 이다.

2. Linked List

 

Array의 삽입, 삭제의 문제를 해결하기 위한 자료구조가 linked list 이다. linked list 는 array와 달리 원소들이 메모리에서 연속적으로 저장되어 있지 않다. 각각의 원소들은 자기 자신 다음에 올 원소(node)와 pointer를 사용해 연결되어 있다. 따라서 삽입과 삭제의 경우에 해당 원소를 제외하고 앞 뒤의 원소의 link를 변경해주어 변경할 수 있다. 따라서 삭제와 삽입을 O(1) 만에 해결할 수 있다.

하지만 검색 과정에서 첫번쨰 원소부터 해당 원소의 위치까지 모든 원소를 확인해야 하기 때문에 O(N)의 시간이 발생한다. 이는 array와 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문이다.

결국 linked list 자료구조는 검색, 삽입, 삭제 모두 O(N)의 time complexity 를 가지게 된다. 그렇지만 tree 구조의 기반이 되는 자료구조로 Tree 구조로 사용되었을 때 그 유용성이 드러난다.

Linked List 자바 구현

public class CustomLinkedList<E> implements CustomList<E> {
    private Node<E> head;

    private Node<E> tail;

    private int size;

    public CustomLinkedList() {}

    private static class Node<E> {
        E item;
        Node<E> next;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
        }
    }

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

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

    @Override
    public boolean contains(Object o) {
        Node<E> node = head;
        while(node != null) {
            if(node.item == o) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

    @Override
    public Object[] toArray() {
        Object[] array = new Object[size];
        Node<E>  node = head;
        for(int i = 0; i < size; i++) {
            array[i] = node.item;
            node = node.next;
        }
        return array;
    }

    @Override
    public boolean add(E e) {
        Node<E> last = tail;
        Node<E> newNode = new Node<E>(tail, e, null);
        tail = newNode;
        if(last == null) {
            head = newNode;
        } else {
            last.next = newNode;
        }
        size++;
        return true;
    }

    @Override
    public void clear() {
        Node<E> node = head;
        while(node != null) {
            Node<E> next = node.next;
            node.item = null;
            node.next = null;
            node = next;
        }
        head = tail = null;
        size = 0;
    }

    private static void checkIndex(int index, int size) {
        if(size <= index) {
            throw new IndexOutOfBoundsException();
        }
    }

    @Override
    public E get(int index) {
        checkIndex(index, size);
        Node<E> node = head;
        for(int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.item;
    }

    @Override
    public E set(int index, E element) {
        checkIndex(index, size);
        Node<E> node = head;
        E oldVal = null;
        for(int i = 0; i < index; i++) {
            node = node.next;
        }
        oldVal = node.item;
        node.item = element;
        return oldVal;
    }

    @Override
    public int indexOf(Object o) {
        Node<E> node = head;
        for(int i = 0; i < size; i++) {
            if(node.item.equals(o)) {
                return i;
            }
            node = node.next;
        }
        return -1;
    }
    
}

 

[reference]

- https://www.geeksforgeeks.org/array-data-structure/#introduction

- https://www.geeksforgeeks.org/data-structures/linked-list/