[Java]Array, LinkedList

·2022년 5월 22일
0

Array(배열)

  • 같은 타입의 데이터가 메모리에 연속적으로 저장되는 구조 (순차적 자료구조)
    • 연속적으로 저장되어 있기 때문에 데이터로의 접근이 쉽다.
    • 생성을 위해서는 연속적인 메모리가 필요하기 때문에 메모리 할당에 제약이 생길 수 있다.
  • 선언된 인덱스 값에 따라 크기가 정해진다.
    • 선언한 인덱스 크키 만큼 데이터를 입력할 경우 낭비되는 메모리가 없다.
    • 선언한 인덱스 크기 보다 적은 데이터를 입력할 경우 메모리가 낭비된다.
  • Cache hit rate가 높다.

배열의 시간복잡도

  • 접근(access)
    배열의 시작 주소와 인덱스 주소를 가지고 사칙연산을 통해 값을 찾아가기 때문에 배열의 접근은 O(1)의 시간복잡도를 갖는다.
  • 검색(search)
    순차 검색으로 배열의 시작부터 값을 만날때까지 확인하기 때문에 O(n)의 시간복잡도를 갖는다.

List

  • 순서가 있는 데이터의 모임
  • 리스트에서 인덱스는 몇 번째 데이터인가 정도의 의미를 가진다 (배열에서의 인덱스는 값에 대한 식별자)
  • cash hit가 어렵다.
  • 자바에서는 크게 ArrayList와 LinkedList 의 두가지 형태의 리스트를 지원한다.

ArrayList

  • 배열을 이용하여 리스트를 구현한 것을 의미한다.
    • 배열을 이용해 구현되었기 때문에 인덱스를 이용한 접근이 빠르다.
  • 빈 메모리를 허용하지 않는다.
    • 맨 앞의 값이나 중간 값을 제거하거나 입력 할 경우 shift를 해야한다.
ArrayList arrayList = new ArrayList(2);		//2칸 크기의 리스트 생성
//데이터 추가
arrayList.add("A");		/* A 		*/
arrayList.add("B");		/* A B 		*/
arrayList.add("C");		/* A B C 	*/
arrayList.add(2, "D");	/* A B D C 	*/
//데이터 삭제
arrayList.remove(0);	/* B D C 	*/
arrayList.remove("D");	/* B C 		*/

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
    
//add at last index
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
    	elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

//add at given index
public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    size = s + 1;
}

private Object[] grow() {
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
        		minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

//remove by index
public E remove(int index) {
	Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

//remove by value
public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: {
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i);
    return true;
}

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

ArrayList의 시간복잡도

  • get(index) : O(1)
  • add(Object)
    • 할당된 메모리 내 추가 : O(1)
    • 할당된 메모리 이상 추가 : O(n)
  • add(int, Object)/remove(Object) : O(n)

✔ 처음이나 중간의 데이터 추가/삭제시 그 뒤의 데이터들을 다 shift해줘야하기 때문에 O(n)의 시간 복잡도가 발생한다.

LinkedList

  • 연결로 리스트를 구현한 것을 의미한다.
    • 한 데이터에서 다음 데이터의 주소를 알고 연결하는 방식
  • 논리적 저장 순서와 물리적 저장 순서가 배열과 다르게 일치하지 않는다.
  • 주소값만 변경하면 되기 때문에 삽입과 삭제 자체는 O(1)이지만 해당 지점까지 접근하기위해 W(n)일 수 있다.
LinkedList linkedList = new LinkedList();
linkedList.add("A");
linkedList.add("B");
linkedList.add(1, "C");
linkedList.remove(1);
linkedList.remove("A");

//add at last index
public boolean add(E e) {
    linkLast(e);
    return true;
}

//add at given index
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
    	linkLast(element);
    else
    	linkBefore(element, node(index));
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

//remove by index
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

//remove by value
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

LinkedList의 시간복잡도

  • get(index) : 순차 접근 방식 사용으로 O(n)
  • getFirst()/getLast() : O(1)
  • add(Object) : O(1)
  • add(index, Object)/remove(index) : O(n+1)

✔ 데이터의 삽입과 삭제가 arrayList보다는 빠르지만 추가되거나 삭제되는 인덱스를 찾기까지 순차 접근을 하기 때문에 접근 위치에 따라서 시간복잡도가 달라질 수 있다.

profile
으쌰으쌰🐜🐜

0개의 댓글