ArrayList and LinkedList

5234 단어
ArrayList and LinkedList
  • ArrayList 는 동적 배열 을 바탕 으로 하 는 데이터 구 조 를 실현 하고 LinkedList 는 링크 를 바탕 으로 하 는 데이터 구 조 를 실현 했다.
  • 랜 덤 액세스 get 과 set 에 대해 Array List 는 LinkedList 보다 낫다 고 생각 합 니 다. LinkedList 는 지침 을 이동 해 야 하기 때 문 입 니 다.
  • 추가 및 삭제 작업 add 와 reove 에 대해 서 는 linedList 가 우세 합 니 다. ArrayList 가 데 이 터 를 이동 해 야 하기 때 문 입 니 다.

  • ArrayList
  • get 방법 은 배열 의 아래 표지 에 따라 데 이 터 를 직접 추출 합 니 다.
  •     public E get(int index) {
            rangeCheck(index);
            return elementData(index);
        }
    
  • set 방법 은 배열 의 아래 표지 에 따라 데 이 터 를 직접 교체 합 니 다.
  •     public E set(int index, E element) {
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }
    
  • add 방법
  •     public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    
       public void add(int index, E element) {
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }
    
  • remove 방법
  •    public E remove(int index) {
            rangeCheck(index);
    
            modCount++;
            E oldValue = elementData(index);
    
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }
    
       public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
       /*
         * Private remove method that skips bounds checking and does not
         * return the value removed.
         */
        private void fastRemove(int index) {
            modCount++;
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
        }
    

    LinkedList
  • get 방법 조회 링크 데이터
  •     public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }
    
    
    
        /**
         * Returns the (non-null) Node at the specified element index.
         */
        Node node(int index) {
            // assert isElementIndex(index);
    
            if (index < (size >> 1)) {
                Node x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
                Node x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }
    
    
  • set 방법 조회 링크 교체 데이터
  •    public E set(int index, E element) {
            checkElementIndex(index);
            Node x = node(index);
            E oldVal = x.item;
            x.item = element;
            return oldVal;
        }
    
  • add 방법
  •     public boolean add(E e) {
            linkLast(e);
            return true;
        }
    
        public void add(int index, E element) {
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
    
  • remove 방법
  •     public boolean remove(Object o) {
            if (o == null) {
                for (Node x = first; x != null; x = x.next) {
                    if (x.item == null) {
                        unlink(x);
                        return true;
                    }
                }
            } else {
                for (Node x = first; x != null; x = x.next) {
                    if (o.equals(x.item)) {
                        unlink(x);
                        return true;
                    }
                }
            }
            return false;
        }
    
        public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }
    
       /**
         * Unlinks non-null node x.
         */
        E unlink(Node x) {
            // assert x != null;
            final E element = x.item;
            final Node next = x.next;
            final Node 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;
        }
    
    

    좋은 웹페이지 즐겨찾기