자바 링크 에서 요소 삭제 의 실현 방법 에 대한 상세 한 설명[하나의 요소 만 삭제 하 는 경우]

본 논문 의 사례 는 자바 링크 에서 요소 삭제 의 실현 방법 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
이 부분 은 이전 절 과 밀접 한 관 계 를 가진다.링크 에서 요 소 를 어떻게 삭제 하 는 지 에 대해 우 리 는 한 걸음 한 걸음 분석 했다.
1.그림 삭제 논리
만약 에 우리 가 링크 에서 색인 이 2 위치 인 요 소 를 삭제 해 야 한다 고 가정 하면 이때 링크 구 조 는 다음 과 같다.

색인 이 2 위치 인 요 소 를 삭제 하려 면 색인 이 2 위치 인 요소 이전의 선행 노드(이때 색인 이 1 인 위치 요소)를 가 져 와 야 하기 때문에 선행 노드 를 기록 하기 위해 변 수 를 prev 로 설계 해 야 합 니 다.
1.초기 변수 prev 가 가상 헤드 노드 dummyHead 를 가리 키 고 있 습 니 다.

2.선행 노드 의 위 치 를 찾 습 니 다.(이 예 에서 선행 노드 가 색인 이 1 인 위치 에 있 는 요소)

이 때 prev 가 기록 한 next 는 삭제 해 야 할 노드 로 delNode 변수 로 기록 합 니 다.

3.삭제 작업
첫 번 째 단계:prev 의 next 를 delNode 의 next 로 가 리 킵 니 다.그림 참조:

코드:

prev.next=delNode.next;

 두 번 째 단계:자바 가 삭 제 된 공간 을 회수 할 수 있 도록 삭제 해 야 할 노드 를 링크 에서 수 동 으로 분리 합 니 다.즉,delNode 의 next 가 null 로 변 합 니 다.

코드:

delNode.next=null;

2.코드 삭제 논리 실현
2.1 링크 에서 제 index(0-based)개 위치의 요 소 를 삭제 하고 삭 제 된 요 소 를 되 돌려 줍 니 다.
먼저,현재 선행 노드 가 가상 헤드 노드 를 가리 키 는 것 을 초기 화한 다음 에 삭 제 된 노드 의 선행 노드 를 찾 아 옮 겨 다 니 며 삭제 논 리 를 실행 합 니 다.

//      index（0-based）       ，        (     ，   )
  public E remove(int index) {
    if (index < 0 || index >= size) {
      throw new IllegalArgumentException("remove failed,Illegal index");
    }

    //       
    Node<E> prev = dummyHead;
    for (int i = 0; i < index; i++) {
      //           
      prev = prev.next;
    }

    Node<E> retNode = prev.next;//      
    prev.next = retNode.next;
    retNode.next = null;
    size--;

    return retNode.e;
  }

2.2 링크 에서 첫 번 째 요 소 를 삭제 하고 삭 제 된 요 소 를 되 돌려 줍 니 다.
reove(int index)방법 으로 이 방법 을 실현 합 니 다.

//           ，       
  public E removeFirst() {
    return remove(0);
  }

2.3 링크 에서 마지막 요 소 를 삭제 하고 삭 제 된 요 소 를 되 돌려 줍 니 다.
reove(int index)방법 으로 이 방법 을 실현 합 니 다.

//            ，       
  public E removeLast() {
    return remove(size - 1);
  }

3.테스트 삭제 논리
이전 테스트 코드 를 기반 으로 논리 코드 를 추가 로 삭제 합 니 다.이 때 모든 테스트 코드 를 붙 입 니 다.

package LinkedList;

public class TestMain {
  public static void main(String[] args) {
    LinkedList<Integer> linkedList = new LinkedList<Integer>();

    System.out.println("============       ============");
    for (int i = 0; i < 5; i++) {
      linkedList.addFirst(i);
      System.out.println(linkedList);
    }

    System.out.println("============    ============");
    linkedList.set(2, 666);
    System.out.println(linkedList);

    System.out.println("============     666  ============");
    linkedList.remove(2);
    System.out.println(linkedList);
  }
}

결 과 는:

 4.링크 의 시간 복잡 도 분석
4.1 작업 시간 복잡 도 추가
(1)링크 끝 에(addLast()를 추가 하려 면 처음부터 옮 겨 다 녀 야 합 니 다.시간 복잡 도 는 O(n)입 니 다.
(2)링크 머리 에(addFirst()를 추가 하고 시간 복잡 도 는 O(1)이다.
(3)링크 의 임 의 위치 에 추가(add(int index,E e),평균 상황 에서 O(n/2)=O(n);

4.2 작업 시간 복잡 도 삭제
(1)링크 의 마지막 요소(removeLast()를 삭제 하려 면 마지막 요소 의 이전 요 소 를 찾 아야 하기 때문에 시간 복잡 도 는 O(n)입 니 다.
(2)링크 의 첫 번 째 요소(removeFirst()를 삭제 하고 시간 복잡 도 는 O(1)입 니 다.
(3)링크 의 임 의 위치 노드(reove(index)를 삭제 하고 평균 상황 에서 시간 복잡 도 는 O(n/2)=O(n)이다.
 
 4.3 수정 작업
링크 가 무 작위 접근 을 지원 하지 않 기 때문에 수정 할 노드 를 찾 을 때 까지 처음부터 찾 아야 하기 때문에 시간 복잡 도 는 O(n)입 니 다.

4.4 찾기 동작
링크 가 무 작위 접근 을 지원 하지 않 기 때문에 필요 한 노드 를 찾 을 때 까지 처음부터 찾 아야 하기 때문에 시간 복잡 도 는 O(n)입 니 다.
 
 위 에서 알 수 있 듯 이 링크 의 추가 작업,삭제 작업,수정 작업,찾기 작업 의 시간 복잡 도 는 모두 O(n)이다.이 를 보면 마음 이 반 쯤 식 었 다.이것 은 mao 를 만 드 는 것 보다 배열 을 만 드 는 것 이 낫 지 않다.사실은 이런 것 이다.배열 에 대해 색인 만 있 으 면 빠 른 방문 을 할 수 있 기 때문이다.그러나 링크 에 있어 우 리 는 링크 헤드 에 만 추가 작업,삭제 작업,찾기 작업 을 하면 그의 시간 복잡 도 는 모두 O(1)이다.이 때 는 배열 과 마찬가지 로 동태 적 이 고 메모리 공간 을 대량으로 낭비 하지 않 는 다.이것 이 바로 그의 장점 이다.링크 는 가장 기본 적 인 동적 데이터 구조 이 고 이 를 바탕 으로 링크 에 대한 응용 이 더 많 을 것 이다.

이 소절 에 대하 여 괜 찮 고 괜찮다 고 생각 하 시 면 추천 해 주세요.감사합니다!
링크 의 소스 코드 https://github.com/FelixBin/dataStructure/tree/master/src/LinkedList
자바 알고리즘 과 관련 된 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.자바 데이터 구조 및 알고리즘 튜 토리 얼,자바 조작 DOM 노드 기술 총화,자바 파일 과 디 렉 터 리 작업 기법 집합과자바 캐 시 작업 기법 집합
본 고 에서 말 한 것 이 여러분 의 자바 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.