[자바 집합 클래스] 링크 드 리스트 소스 분석 (jdk 1.8)

14363 단어 자바 학습
ArrayList 와 LinkedList 는 List 인터페이스의 두 가지 실현 으로 똑 같은 검색, 삽입, 삭제 작업 을 가지 고 있 으 며 바 텀 의 실현 방식 만 다르다.링크 드 리스트 는 양 방향 링크 형식 으로 이 루어 진 집합 류 이다.
그 삭제 작업 은 바 텀 배열 데 이 터 를 이동 할 필요 가 없 기 때문에 링크 노드 지침 만 수정 해 야 하기 때문에 효율 이 비교적 높다.그러나 무 작위 로 방문 할 때 포 지 셔 닝 작업 효율 이 낮 기 때문에 링크 노드 를 옮 겨 다 녀 야 합 니 다.(Array List 와 반대)
목차
  • 데이터 구조
  • 초기 화
  • 확장
  • 찾기 동작
  • 삽입 작업
  • 삭제 작업
  • 대기 열 조작
  • 창고 조작
  • 배열 로 전환
  • 교체 기 실현
  • 데이터 구조
    바 텀 은 양 방향 링크 를 바탕 으로 이 루어 졌 다.또한 요 소 는 null 의 존 재 를 허용 합 니 다.
    그 소스 코드 는 다음 과 같다.
    //           
        private static class Node {
            E item;
            Node next;
            Node prev;
    
            Node(Node prev, E element, Node next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }
        
        //    
        transient int size = 0;
    
        /**
         * Pointer to first node.       
         * Invariant: (first == null && last == null) ||
         *            (first.prev == null && first.item != null)
         */
        transient Node first;
    
        /**
         * Pointer to last node.       
         * Invariant: (first == null && last == null) ||
         *            (last.next == null && last.item != null)
         */
        transient Node last;
    

    초기 화
    링크 때문에 초기 화 할 때 표 의 길 이 를 지정 할 필요 가 없습니다.
    /**
         * Constructs an empty list.
         */
        public LinkedList() {
        }
    
        /**
         * Constructs a list containing the elements of the specified
         * collection, in the order they are returned by the collection's
         * iterator.
         *
         * @param  c the collection whose elements are to be placed into this list
         * @throws NullPointerException if the specified collection is null
         */
        public LinkedList(Collection extends E> c) {
            this();
            addAll(c);
        }
    

    용량 을 늘리다
    링크 때문에 확장 시 새 노드 만 필요 합 니 다.
    찾기 동작
    1. 색인 을 통 해 요소 찾기 (무 작위 접근):
    주의 node(int index) 함수: 색인 을 통 해 해당 하 는 노드 를 찾 습 니 다.(뒤에 여러 가지 방법 을 다 써 요)
    public E get(int index) {
            checkElementIndex(index);
            return node(index).item;
        }
    /**
         * Returns the (non-null) Node at the specified element index.
         */
        //      n/2
        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;
            }
        }
    

    2. 원 소 를 직접 찾기:
    	public int indexOf(Object o) {
            int index = 0;
            if (o == null) {
                for (Node x = first; x != null; x = x.next) {
                    if (x.item == null)
                        return index;
                    index++;
                }
            } else {
                for (Node x = first; x != null; x = x.next) {
                    if (o.equals(x.item))
                        return index;
                    index++;
                }
            }
            return -1;
        }
    
        public int lastIndexOf(Object o) {
            int index = size;
            if (o == null) {
                for (Node x = last; x != null; x = x.prev) {
                    index--;
                    if (x.item == null)
                        return index;
                }
            } else {
                for (Node x = last; x != null; x = x.prev) {
                    index--;
                    if (o.equals(x.item))
                        return index;
                }
            }
            return -1;
        }
    

    삽입 조작
    삽입 작업 을 소개 하기 전에 먼저 삽입 링크 의 위치 에 따라 몇 가지 기본 적 인 삽입 링크 방식 을 소개 합 니 다.
  • (1) 요 소 는 헤드 노드 로 링크 를 삽입 합 니 다.
  • /**
         * Links e as first element.
         */
        private void linkFirst(E e) {
            final Node f = first;
            final Node newNode = new Node<>(null, e, f);
            first = newNode;
            if (f == null)
                last = newNode;
            else
                f.prev = newNode;
            size++;
            modCount++;
        }
    
    	public void addFirst(E e) {
            linkFirst(e);
        }
    
  • (2) 요 소 는 꼬리 노드 로 링크 를 삽입 합 니 다.
  • /**
         * Links e as last element.
         */
        void linkLast(E e) {
            final Node l = last;
            final Node newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
    
    	public void addLast(E e) {
            linkLast(e);
        }
    
  • (3) 요 소 는 노드 e 의 전구 노드 로 링크 를 삽입 합 니 다 (요소 가 링크 의 중간 노드 에 해당 합 니 다):
  •   /**
             * Inserts element e before non-null Node succ.
             */
            void linkBefore(E e, Node succ) {
                // assert succ != null;
                final Node pred = succ.prev;
                final Node newNode = new Node<>(pred, e, succ);
                succ.prev = newNode;
                if (pred == null)
                    first = newNode;
                else
                    pred.next = newNode;
                size++;
                modCount++;
            }
    

    1. 단일 요소 삽입
    public boolean add(E e) {
            linkLast(e);
            return true;
        }
    
    public void add(int index, E element) {
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                // node(index)      
                linkBefore(element, node(index));
        }
    

    2. 집합 삽입:
    	public boolean addAll(Collection extends E> c) {
            return addAll(size, c);
        }
        
    	//    index   (=  index     =   index      )(index 0  )
        public boolean addAll(int index, Collection extends E> c) {
            checkPositionIndex(index);
    
            Object[] a = c.toArray();
            int numNew = a.length;
            if (numNew == 0)
                return false;
            //           ,       
            Node pred, succ;
            //    :   index=size ,  node(index)     ,    
            //(           index-1,    index-1   ?    0          )
            if (index == size) {
                succ = null;
                pred = last;
            } else {
                //   index   
                succ = node(index);
                pred = succ.prev;
            }
    
            for (Object o : a) {
                @SuppressWarnings("unchecked") E e = (E) o;
                //    ,         
                Node newNode = new Node<>(pred, e, null);
                if (pred == null)
                    first = newNode;
                else
                    //            
                    pred.next = newNode;
                pred = newNode;
            }
            //        pred       
            if (succ == null) {
                last = pred;
            } else {
                pred.next = succ;
                succ.prev = pred;
            }
    
            size += numNew;
            modCount++;
            return true;
        }
    

    삭제 작업
    먼저 삭제 노드 가 링크 위치 에 있 는 것 에 따라 몇 가지 기본 적 인 삭제 노드 방식 을 소개 한다.
  • (1) 머리 노드 삭제:
  • /**
         * Unlinks non-null first node f.
         */
        private E unlinkFirst(Node f) {
            // assert f == first && f != null;
            final E element = f.item;
            final Node next = f.next;
            f.item = null;
            f.next = null; // help GC
            first = next;
            if (next == null)
                last = null;
            else
                next.prev = null;
            size--;
            modCount++;
            return element;
        }
    
    	public E removeFirst() {
            final Node f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(f);
        }
    
  • (2) 끝 노드 삭제:
  • /**
         * Unlinks non-null last node l.
         */
        private E unlinkLast(Node l) {
            // assert l == last && l != null;
            final E element = l.item;
            final Node prev = l.prev;
            l.item = null;
            l.prev = null; // help GC
            last = prev;
            if (prev == null)
                first = null;
            else
                prev.next = null;
            size--;
            modCount++;
            return element;
        }
    
    	public E removeLast() {
            final Node l = last;
            if (l == null)
                throw new NoSuchElementException();
            return unlinkLast(l);
        }
    
  • (3) 중간 노드 삭제:
  • /**
         * 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;
        }
    

    1. 색인 을 통 해 요소 삭제:
    	 public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }
    

    2. 지정 한 요소 삭제:
    	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;
        }
    

    대기 열 조작
    주요 동작:
    	//      ,    
    	// first   ,     
        public E peek() {
            final Node f = first;
            return (f == null) ? null : f.item;
        }
    
        // first   ,    
        public E element() {
            return getFirst();
        }
    
        //   (  )
        public E poll() {
            final Node f = first;
            return (f == null) ? null : unlinkFirst(f);
        }
    
    	//   (  )
        public boolean offer(E e) {
            return add(e);
        }
    
    

    창고 조작
    주요 동작:
    	//  ,  
        public void push(E e) {
            addFirst(e);
        }
    
        //  ,  
        public E pop() {
            return removeFirst();
        }
    

    배열 로 전환
     	public Object[] toArray() {
            Object[] result = new Object[size];
            int i = 0;
            for (Node x = first; x != null; x = x.next)
                result[i++] = x.item;
            return result;
        }
    
    @SuppressWarnings("unchecked")
        public  T[] toArray(T[] a) {
            if (a.length < size)
                //       ?         new   ,        class  
                a = (T[])java.lang.reflect.Array.newInstance(
                                    a.getClass().getComponentType(), size);
            int i = 0;
            Object[] result = a;
            for (Node x = first; x != null; x = x.next)
                result[i++] = x.item;
    
            if (a.length > size)
                a[size] = null;
    
            return a;
        }
    

    교체 기 실현
    우선 교체 기 가 무엇 인지 알 아 보 세 요.
  • 자바 의 교체 기 를 깊이 이해
  • 교체 기 에서 fail - fast 메커니즘 의 실현:
  • fail - fast 메커니즘
  • 빠 른 오류 보고 fail - fast 가 말 하고 자 하 는 fail - fast 의 실현 원리 (1)
  • private class ListItr implements ListIterator {
            private Node lastReturned;
            private Node next;
            private int nextIndex;
            private int expectedModCount = modCount;
    
            ListItr(int index) {
                // assert isPositionIndex(index);
                next = (index == size) ? null : node(index);
                nextIndex = index;
            }
    
            public boolean hasNext() {
                return nextIndex < size;
            }
    
            public E next() {
                checkForComodification();
                if (!hasNext())
                    throw new NoSuchElementException();
    
                lastReturned = next;
                next = next.next;
                nextIndex++;
                return lastReturned.item;
            }
    
            public boolean hasPrevious() {
                return nextIndex > 0;
            }
    
            public E previous() {
                checkForComodification();
                if (!hasPrevious())
                    throw new NoSuchElementException();
    
                lastReturned = next = (next == null) ? last : next.prev;
                nextIndex--;
                return lastReturned.item;
            }
    
            public int nextIndex() {
                return nextIndex;
            }
    
            public int previousIndex() {
                return nextIndex - 1;
            }
    
            public void remove() {
                checkForComodification();
                if (lastReturned == null)
                    throw new IllegalStateException();
    
                Node lastNext = lastReturned.next;
                unlink(lastReturned);
                if (next == lastReturned)
                    next = lastNext;
                else
                    nextIndex--;
                lastReturned = null;
                expectedModCount++;
            }
    
            public void set(E e) {
                if (lastReturned == null)
                    throw new IllegalStateException();
                checkForComodification();
                lastReturned.item = e;
            }
    
            public void add(E e) {
                checkForComodification();
                lastReturned = null;
                if (next == null)
                    linkLast(e);
                else
                    linkBefore(e, next);
                nextIndex++;
                expectedModCount++;
            }
    
            public void forEachRemaining(Consumer super E> action) {
                Objects.requireNonNull(action);
                while (modCount == expectedModCount && nextIndex < size) {
                    action.accept(next.item);
                    lastReturned = next;
                    next = next.next;
                    nextIndex++;
                }
                checkForComodification();
            }
    
            final void checkForComodification() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        }
    

    좋은 웹페이지 즐겨찾기