자바 기반 LinkedList

나 는 무뚝뚝 한 감정의 갱신 기계 다.
LinkedList 의 속성:
/ / 링크 의 헤더, 헤더 에 데이터 가 없습니다.Entry 는 링크 류 데이터 구조 입 니 다. 상세 한 내 역 은 뒤 를 보 세 요.
private transient Entry header = new Entry(null, null, null);
/ / LinkedList 의 요소 개수, 즉 현재 용량
private transient int size = 0;
LinkedList 노드 에 대응 하 는 데이터 구조
세 가지 속성 포함: 위의 노드, 다음 노드, 노드 값.
여기 서 알 수 있 듯 이 링크 드 리스트 는 양 방향 링크 로 앞 뒤 두 방향 으로 얻 을 수 있다.private static class Entry {
/ / 현재 노드 의 값
E element;
/ / 다음 노드
Entry next;
/ / 이전 노드
Entry previous;
/ / 노드 의 구조 함수.
Entry(E element, Entry next, Entry previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
LinkedList 의 무 작위 접근
LinkedList 에서 지정 한 위치의 노드 를 가 져 옵 니 다. 매번 처음부터 끝까지 찾 습 니 다. 효율 이 가장 낮 습 니 다.따라서 이런 방식 을 사용 하지 말고 교체 기 나 for each 방식 을 사용 해 야 한다.

private Entry<E> entry(int index) {
        if (index < 0 || index >= size)            throw new IndexOutOfBoundsException("Index: "+index+  ", Size: "+size);

      Entry<E> e = header;

        //   index    。

        //  index      1/2,       

        if (index < (size >> 1)) {

            for (int i = 0; i <= index; i++)

                e = e.next;

        } else {

      //   ，      

            for (int i = size; i > index; i--)

              e = e.previous;

        }

      return e;

    }

LinkedList 교체 기:
반복 시간 초기 화 교체 기 는 처음부터 끝까지 위 치 를 찾 은 후 매번 다음 것 만 조회 하면 됩 니 다.

private class ListItr implements ListIterator<E> {

        //                 private Entry lastReturned = header;

        //      

        private Entry<E> next;

        //            

      private int nextIndex;

        //        。    fail-fast  。        private int expectedModCount = modCount;

        //     。

        //  index        

        ListItr(int index) {

            // index      

            if (index < 0 || index > size)                throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size);

            //   index            ，             ；

            if (index < (size >> 1)) {

                next = header.next;                          for (nextIndex=0; nextIndex<index; nextIndex++)

                  next = next.next;

            } else {

//   ，           

                next = header;                for (nextIndex=size; nextIndex>index; nextIndex--)

                    next = next.previous;

          }

      }

//   fail-fast  ，    。

        final void checkForComodification() {            if (modCount != expectedModCount)            throw new ConcurrentModificationException();

      }

    }

linkedList 의 직렬 화 와 반 직렬 화:
먼저 용량 을 쓰 고 구체 적 인 값 을 쓴다.먼저 용량 을 읽 은 다음 에 각 구체 적 인 값 을 읽는다.

  //  LinkedList   ，           

private void writeObject(java.io.ObjectOutputStream s)

        throws java.io.IOException {

        s.defaultWriteObject();

        //     

        s.writeInt(size);

      //                             for (Entry e = header.next; e != header; e = e.next)

          s.writeObject(e.element);

    }

  private void readObject(java.io.ObjectInputStream s)        throws java.io.IOException, ClassNotFoundException {

        s.defaultReadObject();

        //          

        int size = s.readInt();

        //       

        header = new Entry<E>(null, null, null);

      header.next = header.previous = header;

      //       “   ”         

        for (int i=0; i<size; i++)            addBefore((E)s.readObject(), header);

  }