데이터 구조 - 링크 목록, ArrayList, LinkedList

제목: '데이터 구조 - 링크 목록, 배열 목록, 링크 목록' 날짜: 2019 - 11 - 16 10: 42: 41 categories:

데이터 구조 태그:

데이터 구조

링크

추상 데이터 형식 ADT

한 조 의 조작 을 가 진 일부 대상 의 집합

특별한 추상 적 인 유형 - 표 ADT
무엇이 시계 입 니까?
가장 간단 한 정수 표 -> 한 무리의 정수 로 구 성 된 배열 로 표 라 고 볼 수 있다.

//        
int[] arr = new int[10];
...
//       
int[] newArr = new int[arr.length*2];
for(int i=0;i<arr.length;i++){
    newArr[i] = arr[i];
}
arr =newArr;

배열 의 실현 은 선형 으로 실 행 된 것 이 고 그 중의 검색 작업 도 상수 시간 이지 만 삽입 과 삭 제 는 비 싼 비용 이 숨 어 있다.둘 다 최 악의 경 우 는 O (N) 입 니 다.
단순 링크
그래서 삽입 과 삭제 비용 을 피하 기 위해 링크 가 생 겼 습 니 다.링크 는 하나의 노드 로 구성 되 어 있 으 며 연속 적 인 메모리 에 저장 하 는 것 을 제한 하지 않 습 니 다.
노드
모든 노드 는 하나의 표 요 소 를 포함 하고 후계 노드 를 포함 하 는 체인 링크 를 포함한다.

//    
LinkNode class{
    Object var;
    LinkNode next;
}

링크 의 노드 삭제 와 삽입 은 상수 시간 만 필요 합 니 다.
먼저 삭제 할 노드 위치 나 삽입 할 노드 위 치 를 찾 습 니 다.
이 노드 의 이전 노드 를 삭제 하고 이 노드 의 후계 노드 를 가리 키 면 됩 니 다.
삽입 노드 의 이전 노드 를 찾 고 이전 노드 의 후계 노드 를 이 노드 로 가리 키 며 이전 노드 를 이 노드 로 가리 킵 니 다.
더 블 링크
단일 체인 시트 의 부족 한 점 은 꼬리 노드 에 대한 삭 제 는 마지막 노드 의 항목 을 찾 아 next 체인 을 null 로 바 꾼 다음 에 마지막 노드 를 가 진 체인 을 업데이트 해 야 한 다 는 것 이다.그러나 전형 적 인 링크 에서 모든 노드 는 다음 노드 를 저장 하고 마지막 노드 의 전구 노드 에 대한 정 보 를 제공 하지 않 습 니 다.
단일 체인 시트 의 삭 제 는 보조 노드 에 의존 해 야 하고, 양 방향 링크 는 직접 삭제 할 수 있다.
이에 대해 양 방향 링크 가 생각 나 서 모든 노드 가 표 에 있 는 전구 노드 를 가리 키 는 체인 을 가지 게 한다.
JAVA 의 Collections API 표
집합 개념 은 자바 에서 Collection 인터페이스 로 추상 적 이 며, 같은 유형의 대상 을 저장 합 니 다.

//    
public interface Collection<E> extends Iterable<E> {
 	int size();
     boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator(); //      Iterable    Iterator  
    boolean add(E e);
    boolean remove(Object o);
}

Collection 인 터 페 이 스 는 Iterator 인 터 페 이 스 를 확장 하여 Iterator 인터페이스 에서 강 화 된 for 순환 을 실현 합 니 다.

//Iterator  
public interface Iterator<E> {
    boolean hasNext(); 
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

List 인터페이스, ArrayList 클래스, LinkedList 클래스
List 인 터 페 이 스 는 표 의 추상 이자 Collection 을 계승 했다.

public interface List<E> extends Collection<E> {
     int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator(); 
    Object[] toArray();

    
    E get(int index);
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);
    
    / ** 
        *           ，    
        *               。
        *           {@link ListIterator＃next next}         。 
        *    {@link ListIterator＃previous previous} 
        *             。 
        * * @param index                 （    {@link ListIterator＃next next}）
        * @                （      ） ，           
        * @throws IndexOutOfBoundsException        
        *（{@code index <0 || index> size（）}）* /
    ListIterator<E> listIterator(int index); 

Array List 와 LinkedList 는 List 에 대한 두 가지 실현 이다.
ArrayList 싱글 체인 시트

성장 가능 한 배열 실현

장점 은 get 과 set 의 호출 에 상수 시간

이 걸 린 다 는 것 이다.

단점 은 add 와 remove 의 대가 가 비싸다

ArrayList 의 실현 과 분석
링크 리스트 더 블 링크

은 쌍 사슬 표 의 실현

장점 은 add 와 reove 의 씀 씀 이 가 적다

는 것 이다.

또한 addFirst, removeFirst, addLast, removeLast, getFirst, getLast 등 방법

을 제공 합 니 다.

단점 은 색인 이 쉽 지 않 고 get 호출 이 비 싼 것

이다.
미 완성 계속...