자바 링크 에 요 소 를 추가 하 는 원리 와 실현 방법 에 대한 상세 한 설명

본 논문 의 사례 는 자바 링크 에 요 소 를 추가 하 는 원리 와 실현 방법 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
1.링크 의 헤드 노드 도입
1.1 기본 적 인 링크 구조:

1.2 링크 에 있어 링크 의 모든 노드 를 방문 하려 면 링크 의 머리 를 저장 해 야 한다.만약 에 링크 의 머리 노드 가 head 라면 링크 의 첫 번 째 노드 를 가리킨다.그림 과 같다.

1.3 코드 를 사용 하여 이때 의 링크 를 표시 합 니 다.

//     
  private Node head;

  //    
  private int size;


  //       
  public LinkedList() {
    head = null;
    size = 0;
  }

  //          
  public int getSize() {
    return size;
  }

  //        
  public boolean isEmpty() {
    return size == 0;
  }

 2.체인 헤더 에 요소 추가
2.1 초기 에 링크 가 다음 과 같다 고 가정 합 니 다.

2.2 체인 헤더 에 666 요 소 를 추가 하려 면 먼저 666 을 한 노드 에 넣 고 노드 에 이 요소 와 해당 하 는 next 를 저장 해 야 한다.

동작 은 다음 과 같 습 니 다.
첫 번 째 단계:현재 666 이 노드(node)의 next 를 head 로 가리 키 고 코드 는 다음 과 같 습 니 다.

node.next=head

그림 은 다음 과 같다.

두 번 째 단계:그리고 헤드 를 새로운 노드 666 로 가리 키 기

head=node

그림 은 다음 과 같다.

첫 번 째,두 번 째 단 계 를 통 해 우 리 는 새로운 노드 를 첫 번 째 절 에 추가 하 는 데 성공 했다.이 때 node 이 변 수 는 이 라운드 의 작업 을 끝 냈 고 결 과 는 다음 과 같 습 니 다.

2.3 체인 헤더 에 새로운 요 소 를 추가 하 는 관련 코드

 //          e
  public void addFirst(E e) {
    Node node = new Node(e);
    node.next = head;
    head = node;


    size++;
  }

...과 같다

 //          e
  public void addFirst(E e) {
    head = new Node(e, head);
    size++;
  }

2.4 링크 중간 에 요 소 를 추가 합 니 다.
초기 링크 를 다음 과 같이 가정 합 니 다.

색인 이 2 인 위치 에 요소 666 을 추가 해 야 한다 고 가정 합 니 다.
작업 단계:
1):666 이 노드 를 만 듭 니 다.

2):하나의 변수 prev 를 사용 하여 노드 를 삽입 해 야 하 는 곳 의 앞 노드 를 표시 합 니 다.처음에 prev 와 머리 노드 head 는 같 았 습 니 다.

색인 이 2 인 위치 에 새 요 소 를 삽입 해 야 합 니 다.색인 이 2 인 이전 위치(색인 이 1)를 찾 은 다음 prev 를 1 노드 로 가리 키 면 됩 니 다.

3):원소 추가 작업 진행
첫 번 째 단계:node 의 next 를 prev 의 다음 노드 요소 로 가리 키 기

node.next=prev.next

두 번 째 단계:prev 의 next 를 node 로 가리 키 기

prev.next=node

첫 번 째,두 번 째 단 계 를 통 해 새로운 요 소 를 색인 이 2 인 곳 에 삽입 할 수 있 습 니 다.
 위 에서 알 수 있 듯 이 링크 에 요 소 를 추가 하 는 관건 은 추가 할 노드 의 앞 노드 를 찾 는 것 이다.따라서 색인 이 0 인 노드 에 요 소 를 추가 하려 면 따로 처리 해 야 한다.
링크 중간 에 요 소 를 추가 하 는 코드:

 //    index(0--based)         e  (     ，   )

  public void add(int index, E e) {
    if (index < 0 || index > size) {
      throw new IllegalArgumentException("     ");
    }

    //          
    if (index == 0) {
      addFirst(e);
    } else {
      Node prev = head;
      for (int i = 0; i < index - 1; i++) {//                 
        prev = prev.next;
      }

      Node node = new Node(e);
      node.next = prev.next;
      prev.next = node;

      size++;
    }

  }

이 때 코드 는 다음 과 같 습 니 다.

 //    index(0--based)         e  (     ，   )

  public void add(int index, E e) {
    if (index < 0 || index > size) {
      throw new IllegalArgumentException("     ");
    }

    //          
    if (index == 0) {
      addFirst(e);
    } else {
      Node prev = head;
      for (int i = 0; i < index - 1; i++) {//                 
        prev = prev.next;
      }

//      Node node = new Node(e);
//      node.next = prev.next;
//      prev.next = node;

      prev.next=new Node(e,prev.next);

      size++;
    }

  }

3.링크 끝 에 요소 추가
위 와 같은 add()방법 을 다시 사용 합 니 다.

 //           
  public void addLast(E e){
    add(size,e);
  }

이 소절 전체 코드:

package LinkedList;

public class LinkedList<E> {
  // Node           
  private class Node<E> {
    public E e;
    public Node next;


    //         

    public Node(E e, Node next) {
      this.e = e;
      this.next = next;
    }

    //         
    public Node(E e) {
      this.e = e;
      this.next = null;
    }

    //      
    public Node() {
      this(null, null);
    }

    @Override
    public String toString() {
      return e.toString();
    }
  }

  //     
  private Node head;

  //    
  private int size;


  //       
  public LinkedList() {
    head = null;
    size = 0;
  }

  //          
  public int getSize() {
    return size;
  }

  //        
  public boolean isEmpty() {
    return size == 0;
  }


  //          e
  public void addFirst(E e) {
    head = new Node(e, head);
    size++;
  }

  //    index(0--based)         e  (     ，   )

  public void add(int index, E e) {
    if (index < 0 || index > size) {
      throw new IllegalArgumentException("     ");
    }

    //          
    if (index == 0) {
      addFirst(e);
    } else {
      Node prev = head;
      for (int i = 0; i < index - 1; i++) {//                 
        prev = prev.next;
      }

//      Node node = new Node(e);
//      node.next = prev.next;
//      prev.next = node;

      prev.next=new Node(e,prev.next);

      size++;
    }

  }

  //           
  public void addLast(E e){
    add(size,e);
  }
}

자바 알고리즘 과 관련 된 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 고 에서 말 한 것 이 여러분 의 자바 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.