02-LinkedList

글 목록

LinkedList

1. 약술

2. 속성 과 데이터 구조

2.1 속성

2.2 데이터 구조

2.3 구조 방법

3. 중요 한 방법

3.1 원소 첨가

3.1.1 add

3.1.2 두부 첨가

3.1.3 꼬리 부분 추가

3.1.4 지정 위치 추가

3.2 원소 삭제

3.2.1 지정 위치 제거

3.2.2 두미 제거

3.2.3 꼬리 제거

3.2.4 지정 치 제거

3.3 수정 요소

3.4 조회 요소

3.4.1 드 롭 다운 획득

3.4.2 머리 획득

3.4.3 꼬리 부분 획득

3.4.4 값 에 따라 획득

3.5 대기 열 조작

4. ArrayList 와 LinkedList 비교

4.1 기본 대비

4.2 성능 대비

5. 소결

6. 참고

LinkedList
약술 하 다

LinkedList 는 링크 를 바탕 으로 하 는 List 집합 으로 내부 에서 링크 를 사용 하여 요 소 를 저장 합 니 다.

2. 속성 과 데이터 구조
2.1 속성

//   
transient Node<E> first;
//   
transient Node<E> last;

2.2 데이터 구조

LinkedList 에서 Node 를 사용 하여 링크 노드 를 표시 합 니 다. 구조 가 간단 합 니 다. 데이터 도 메 인 item 을 제외 하고 전구 지침 과 후계 지침

도 포함 되 어 있 습 니 다.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}    

2.3 구조 방법

LinkedList 의 구조 방법 은 과부하 가 있 지만 내부 속성 이 적 고 한도 값, 기본 용량 등 매개 변수 가 없 기 때문에 기본 적 인 구조 방법 은 아무것도 하지 않 습 니 다.

    public LinkedList() {
    }

3. 중요 한 방법
3.1 요소 추가
3.1.1 add 추가

add 방법 은 기본적으로 끝 에 추가 합 니 다.

public boolean add(E e) {
    linkLast(e);
    return true;
}

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

3.1.2 머리 추가

머리 에 첨가

public void addFirst(E e) {
    linkFirst(e);
}
    
private void linkFirst(E e) {
    final Node<E> f = first;
    //1.     ，     
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    //2.     null，           
    if (f == null)
        last = newNode;
    else
        //3.      null，              
        f.prev = newNode;
    size++;
    modCount++;
}

3.1.3 꼬리 부분 추가

linkLast 앞에서 분 석 했 습 니 다. add 와 거의 등가

 public void addLast(E e) {
        linkLast(e);
    }

3.1.4 지정 위치 추가

add 방법 은 지정 한 index 에 추가 할 수 있 습 니 다. index 에 있 는 대상 요 소 를 먼저 찾 은 다음 에 링크 의 지침 작업 을 통 해 요 소 를 추가 할 수 있 습 니 다

    public void add(int index, E element) {
        //1.    ，       0 size  
        checkPositionIndex(index);
        //2.        ，     
        if (index == size)
            linkLast(element);
        //3.       ，         ，node     index   
        else
            linkBefore(element, node(index));
    }

linkBefore: 지정 한 요소 앞 에 링크 하고 양 방향 지침 을 수정 하면 됩 니 다

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

linkLast: 끝 에 링크

    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++;
    }

3.2 요소 삭제
3.2.1 지 정 된 위치 제거

remove 는 지정 한 index 에 있 는 요 소 를 삭제 합 니 다. 먼저 node 방법 으로 요 소 를 찾 은 다음 에 unlink 를 호출 하여 요소 의 앞 구 를 연결 하여 자 체 를 제거 해 야 합 니 다

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

3.2.2 두미 제거

removeFirst 두부 제거

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

3.2.3 끝부분 제거

    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

3.2.4 지정 값 제거

폭력 조회 만 가능 하고 제거, 복잡 도 O (N)

    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;
    }

3.3 수정 요소

먼저 위 치 를 정 한 다음 에 수정 하고 낡은 값 으로 돌아 가기

    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

3.4 조회 요소
3.4.1 드 롭 다운 획득

아래 표 시 를 통 해 얻 을 수 있 습 니 다. 얻 는 과정 이 재 미 있 습 니 다. 앞부분 에서 처음부터 옮 겨 다 니 면 후반 부분 에서 꼬리 부분 을 옮 겨 다 니 면 양 방향 링크 에서 요 소 를 적 게 찾 으 려 고 합 니 다. 그러나 복잡 도 는 여전히 O (N)

입 니 다.

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
        Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

3.4.2 머리 획득

    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

3.4.3 꼬리 획득

    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

3.4.4 값 에 따라 획득

값 에 따라 조회 하면 폭력 적 으로 조회 한 다음 에 제거, 복잡 도 O (N)

    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

3.5 대기 열 조작

peek: 머리 요 소 를 가 져 오지 만 요 소 를 제거 하지 않 습 니 다.(element 방법 은 peek 의 방법 작용 과 마찬가지 로 요소 가 없 을 때 peek 가 null 로 돌아 가 는 것 과 차이 가 있 지만 element 가 이상 을 던 집 니 다)

    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

    public E element() {
        return getFirst();
    }

poll: 머리 요 소 를 제거 하고 이 요 소 를 되 돌려 줍 니 다.(remove 방법 은 poll 방법의 작용 과 마찬가지 로 원소 가 없 을 때 poll 이 null 로 되 돌아 오지 만 remove 가 이상 을 던 지 는 것 과 차이 가 있다)

    public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
    
    public E remove() {
        return removeFirst();
    }

그리고 일부 대열 의 방법 도 있다. 예 를 들 어 remove, offer, offerFirst, offerLast, peekFirst, peekLast, pollFirst, pollLast, push, pop 등 은 일일이 제시 하지 않 는 다

.
4. Array List 와 LinkedList 비교
4.1 기본 대비
대비 차원
ArrayList
LinkedList
데이터 구조
배열
체인 테이블
공간 효율
노드 는 낭 비 를 보지 못 했 지만 확장 은 공간 낭비 가 있 을 수 있다.
각 노드 마다 추가 포인터 필드 가 필요 합 니 다.
우세 하 다.
임 의 접근
머리 삽입, 다른 성능 은 ArrayList 에 비해 차지 하지 않 습 니 다. 대기 열 지원 Api
기본 용량
10
없다
용량 을 늘리다
1.5 배
확장 할 필요 가 없다.
4.2 성능 대비

성능 비 교 는 참고 글 [1] 을 읽 을 수 있 고 이 글 의 결론

을 직접 인용 할 수 있다.
데이터 양 \ 삽입 위치
머리 부분
가운데
끝부분
무 작위
백.
효율 이 일정 하 다.
효율 이 일정 하 다.
효율 이 일정 하 다.
효율 이 일정 하 다.
천.
LinkedList 삽입 속도
효율 이 일정 하 다.
효율 이 일정 하 다.
ArrayList 삽입 속도
만.
LinkedList 삽입 속도
ArrayList 삽입 속도
효율 이 일정 하 다.
ArrayList 삽입 속도
십 만
LinkedList 삽입 속도
ArrayList 삽입 속도
ArrayList 삽입 속도
ArrayList 삽입 속도
백만
LinkedList 삽입 속도
ArrayList 삽입 속도
ArrayList 삽입 속도
ArrayList 삽입 속도

표 에서 기본적으로 볼 수 있 듯 이 LinkedList 는 머리 에 삽입 할 때 만 성능 을 차지 합 니 다. 이때 ArrayList 는 대량의 데 이 터 를 뒤로 복사 해 야 하지만 나머지 상황 은 ArrayList 가 좋 습 니 다.

중간 위치의 삽입 은 링크 드 리스트 가 옮 겨 다 니 는 요소 가 많 기 때문에 더 느 립 니 다. Array List 는 복사 가 필요 하지만 성능 이 오히려 좋 습 니 다.마찬가지 로 끝부분 도 마찬가지 입 니 다. LinkedList 는 옮 겨 다 니 는 것 이 적 습 니 다. 그러나 Array List 는 copy 가 필요 한 것 도 적 고 Array List 의 성능 이 오히려 좋 습 니 다

.

요소 가 비교적 많 을 때 Array List 의 확대 가 가 져 온 장점 이 뚜렷 하고 1.5 배의 확 대 는 빈번 한 확 대 를 피 할 수 있다

.

다른 저장 공간 에서 Array List 는 일부 확 장 된 공간 을 낭비 할 수 있 고 LinkedList 는 각 노드 에 두 개의 지침 도 메 인 을 추가 로 저장 해 야 한다

.

LinkedList 의 장점 은 대열 의 기본 적 인 실현

을 제공 하 는 데 있다.
소결

LinkedList 자체 의 작업 은 기본 적 인 추가 작업 은 링크 의 끝 부분 에 있 기 때문에 빠 릅 니 다. 링크 의 끝 부분 이 아니라면 index 의 추가 와 삭 제 는 index 에 따라 요소 의 위 치 를 미리 찾 은 다음 에 지침 을 통 해 조작 해 야 합 니 다.포인터 조작 은 매우 빠 르 지만 포 지 셔 닝 과정 은 위치 가 전반 부 에 있 는 지 후반 부 에 따라 예전 부터 옮 겨 다 니 는 지 꼬리 부터 옮 겨 다 니 는 지 결정 하기 때문에 LinkedList 의 추가 삭제 작업 도 반드시 '빠 른' 것 은 아니다.

LinkedList 의 조회 조작 은 앞에서 언급 한 것 이다. 판단 구역 을 옮 겨 다 니 며 검색 한 결과 LinkedList 의 조회 효율 이 높 지 않 고 삭제 할 때 먼저 조회 해 야 한다. LinkedList 가 링크 시트 조작 이 라 고 쉽게 생각 하지 않 으 면 삭제 가 빠르다. 앞의 테스트 결 과 는 참고 할 수 있다

.

LinkedList 는 대기 열 방법 을 추가 로 제공 합 니 다. 이것 은 LinkedList 의 장점 입 니 다. Array List 는 갖 추 지 못 한 것 입 니 다

참고

[1] JAVA 시리즈 탐색 (2) LinkedList 삽입 데이터 가 정말 ArrayList 보다 빠 릅 니까?

[2] ArrayList