자바 단 방향 링크 의 기본 기능 에 대한 상세 한 설명 실현

머리말
최근 에 데이터 구조 와 알고리즘 을 돌 이 켜 보면 일부 알고리즘 문 제 는 스 택 의 사상 을 사 용 했 고 스 택 하면 링크 를 말 할 수 밖 에 없 었 다.배열 과 링크 는 모두 선형 저장 구조의 기초 이 고 스 택 과 대기 열 은 모두 선형 저장 구조의 응용 입 니 다~
본 고 는 주로 단일 체인 표 의 기초 지식 점 을 설명 하고 간단 한 입문 을 합 니 다~잘못된 부분 이 있 으 면 지적 해 주 십시오.
2.회고 와 지신
링크 하면 우리 먼저 배열 을 들 어 봅 시다.배열 과 비교 하면 링크 와 같은 저장 구 조 를 잘 이해 할 수 있 습 니 다.
2.1 회고 배열
배열 우 리 는 C,자바 든 모두 배 웠 다.
  • 배열 은 연속 적 인 저장 선형 구조 로 요소 의 유형 이 같 고 크기 가 같다
  • .

    배열 의 장점:
  • 액세스 속도 가 빠르다
  • 배열 의 단점:
  • 배열 의 길 이 를 미리 알 아야 한다
  • 삭제 요 소 를 삽입 하 는 것 이 느 립 니 다
  • 공간 은 보통 제한 이 있다
  • 큰 연속 메모리 블록
  • 이 필요 합 니 다.
  • 삭제 요 소 를 삽입 하 는 효율 이 낮다
  • 2.2 링크 설명
    배열 을 보고 우리 의 링크 로 돌아 갑 니 다.
  • 링크 는 분 산 된 저장 선형 구조
  • 이다.
    n 개의 노드 가 분 산 된 분 배 는 서로 지침 을 통 해 연결 되 고 모든 노드 는 하나의 전구 노드 만 있 으 며 모든 노드 는 하나의 후속 노드 만 있 고 첫 번 째 노드 는 전구 노드 가 없 으 며 꼬리 노드 는 후속 노드 가 없다.

    링크 장점:
  • 공간 제한 없 음
  • 삭제 요 소 를 삽입 하 는 것 이 빠르다
  • 링크 단점:
  • 액세스 속도 가 느 립 니 다
  • 링크 관련 용어 소 개 는 위 에 있 는 그림 을 통 해 설명 하 겠 습 니 다.

    체인 시 계 를 확인 하려 면 헤드 포인터 만 있 으 면 헤드 포인터 로 전체 체인 시 계 를 유도 할 수 있 습 니 다~
    체인 시 계 는 또 여러 종류 로 나 뉘 었 다.
    1.단 방향 링크
  • 한 노드 가 다음 노드 를 가리킨다
  • 2.양 방향 링크
  • 한 노드 에 두 개의 지침 역 이 있다
  • 3.순환 링크
  • 모든 노드 를 통 해 다른 모든 노드 를 찾 을 수 있 고 두 가지(양 방향/단 방향)링크 의 마지막 노드 를 첫 번 째 노드 로 가리 키 며 순환
  • 을 실현 할 수 있다.
    링크 를 조작 할 때 항상 기억 해 야 할 것 은:
    노드 에서 포인터 영역 이 가리 키 는 것 은 하나의 노드 입 니 다!
    3.자바 구현 링크
    알고리즘:
  • 옮 겨 다 니 기
  • 찾기
  • 비우 기
  • 소각
  • 길이 구하 기
  • 정렬
  • 노드 삭제
  • 노드 삽입
  • 우선,우 리 는 하나의 종 류 를 노드 로 정의 한다.
  • 데이터 필드
  • 포인터 영역
  • 조작 편 의 를 위해 서 나 는 바로 Public 로 정의 했다.
    
    public class Node {
    
     //   
     public int data;
     //   ,       
     public Node next;
     public Node() {
     }
    
     public Node(int data) {
     this.data = data;
     }
    
     public Node(int data, Node next) {
     this.data = data;
     this.next = next;
     }
    }
    3.1 링크 만 들 기(노드 증가)
    링크 에 데이터 삽입:
  • 끝 노드 를 찾 아 삽입 하기
  • 머리 노드.next 가 null 이 고 while 순환 을 하지 않 아 도 머리 노드 와 새 노드 를 연결 합 니 다(저 는 head 노드 를 초기 화 했 기 때문에 머리 노드 가 null 인지 판단 할 필요 가 없습니다)~
  • 
     /**
     *        
     *
     * @param value       
     */
     public static void addData(int value) {
     //         
     Node newNode = new Node(value);
     //    
     Node temp = head;
     //      
     while (temp.next != null) {
     temp = temp.next;
     }
     //         .next null    ~
     temp.next = newNode;
     }
    3.2 링크 옮 겨 다 니 기
    위 에 우리 가 추가 방법 을 만 들 었 으 니 이 제 는 제대로 되 었 는 지 살 펴 보 자~~
    첫 번 째 노드 부터 뒤쪽 노드 에 데이터 가 없 을 때 까지 계속 찾 습 니 다.
    
     /**
     *     
     *
     * @param head    
     */
     public static void traverse(Node head) {
     //    ,      
     Node temp = head.next;
     while (temp != null) {
     System.out.println("     Java3y:" + temp.data);
     //     
     temp = temp.next;
     }
     }
    
    결과:
     
    3.3 삽입 노드
  • 하나의 노드 를 링크 에 삽입 하려 면 먼저 이 위치 가 합 법 적 인지 판단 해 야 삽입 할 수 있 습 니 다~
  • 삽입 하고 싶 은 위치의 이전 노드 를 찾 으 면 됩 니 다~
  • 
     /**
     *     
     *
     * @param head    
     * @param index       
     * @param value      
     */
     public static void insertNode(Node head, int index, int value) {
     //              ,
     if (index < 1 || index > linkListLength(head) + 1) {
     System.out.println("       。");
     return;
     }
     //    ,      
     Node temp = head;
     //         
     int currentPos = 0;
     //         
     Node insertNode = new Node(value);
     while (temp.next != null) {
     //           
     if ((index - 1) == currentPos) {
     //temp         
     //                      
     insertNode.next = temp.next;
     //                  
     temp.next = insertNode;
     return;
     }
     currentPos++;
     temp = temp.next;
     }
     }
    3.4 링크 의 길 이 를 가 져 옵 니 다.
    링크 의 길 이 를 가 져 오 는 것 은 간단 합 니 다.한 노드+1 을 얻 을 때마다~
    
     /**
     *        
     * @param head    
     */
     public static int linkListLength(Node head) {
     int length = 0;
     //    ,      
     Node temp = head.next;
     //      
     while (temp != null) {
     length++;
     temp = temp.next;
     }
     return length;
     }
    3.5 노드 삭제
    특정한 위치 에 있 는 노드 를 삭제 하 는 것 은 삽입 노드 와 비슷 하고 똑 같이 이전 노드 를 찾 아야 합 니 다.이전 노드 의 포인터 영역 을 바 꾸 면 삭제 할 수 있 습 니 다~
    
     /**
     *         
     *
     * @param head    
     * @param index       
     */
     public static void deleteNode(Node head, int index) {
     //              ,
     if (index < 1 || index > linkListLength(head) + 1) {
      System.out.println("       。");
      return;
     }
    
     //    ,      
     Node temp = head;
     //         
     int currentPos = 0;
     while (temp.next != null) {
      //           
      if ((index - 1) == currentPos) {
      //temp         
      //temp.next           
      //            
      Node deleteNode = temp.next;
      //                      
      temp.next = deleteNode.next;
      //Java    ,      null        (    ,        ~)
      deleteNode = null;
      return;
      }
      currentPos++;
      temp = temp.next;
     }
     }
    3.6 링크 정렬
    앞에서 이미 8 가지 정렬 알고리즘 을 말 했 습 니 다[8 가지 정렬 알고리즘 총화].이번 에는 간단하게 거품 을 일 으 켜 정렬 합 시다.
    
     /**
     *        
     *
     * @param head
     *
     */
     public static void sortLinkList(Node head) {
     Node currentNode;
     Node nextNode;
     for (currentNode = head.next; currentNode.next != null; currentNode = currentNode.next) {
      for (nextNode = head.next; nextNode.next != null; nextNode = nextNode.next) {
      if (nextNode.data > nextNode.next.data) {
       int temp = nextNode.data;
       nextNode.data = nextNode.next.data;
       nextNode.next.data = temp;
      }
      }
     }
     }
    3.7 링크 의 마지막 k 번 째 노드 를 찾 습 니 다.
    이 알고리즘 은 매우 재 미 있 습 니 다.두 개의 포인터 p1,p2 를 설정 하여 p2 가 p1 보다 k 개의 노드 를 빠르게 하 는 동시에 뒤로 옮 겨 다 닙 니 다.p2 가 비어 있 으 면 p1 은 꼴찌 k 개의 노드 입 니 다.
    
     /**
     *         k   (      p1、p2, p2 p1 k   ,      , p2  , p1    k   
     *
     * @param head
     * @param k    k   
     */
     public static Node findKNode(Node head, int k) {
     if (k < 1 || k > linkListLength(head))
      return null;
     Node p1 = head;
     Node p2 = head;
     // p2  p1 k   
     for (int i = 0; i < k - 1; i++)
      p2 = p2.next;
     //   p2 null,  p1     k    
     while (p2.next != null) {
    
      p2 = p2.next;
      p1 = p1.next;
     }
     return p1;
     }
    3.8 링크 중복 데이터 삭제
    거품 과 정렬 차이 가 많 지 않 아,그것 만 같 으 면 지 울 수 있어~
    
     /**
     *         (      ,       )
     *
     * @param head    
     */
     public static void deleteDuplecate(Node head) {
     //    ,(      -->        )
     Node temp = head.next;
    
     //    (   )      
     Node nextNode = temp.next;
     while (temp.next != null) {
      while (nextNode.next != null) {
      if (nextNode.next.data == nextNode.data) {
       //        (           )
       nextNode.next = nextNode.next.next;
      } else {
    
       //     
       nextNode = nextNode.next;
      }
      }
      //     
      temp = temp.next;
     }
     }
    3.9 조회 링크 의 중간 노드
    이 알고리즘 도 매우 재 미 있 습 니 다.하 나 는 매번 한 걸음 씩 걷 고 하 나 는 두 걸음 씩 걷 고 두 걸음 으로 옮 겨 다 니 며 한 걸음 씩 가 는 지침 입 니 다.그것 이 바로 중간 노드 입 니 다.
    
     /**
     *           
     */
     public static Node searchMid(Node head) {
     Node p1 = head;
     Node p2 = head;
     //      ,     ,   null,             
     while (p2 != null && p2.next != null && p2.next.next != null) {
      p1 = p1.next;
      p2 = p2.next.next;
     }
     return p1;
     }
    3.10 재 귀 를 통 해 끝 에서 끝까지 단일 체인 표를 출력 한다.
    
     /**
     *              
     *
     * @param head    
     */
     public static void printListReversely(Node head) {
     if (head != null) {
      printListReversely(head.next);
      System.out.println(head.data);
     }
     }
    3.11 반전 링크
    
     /**
     *        
     *
     * @param node       
     */
     public static Node reverseLinkList(Node node) {
     Node prev ;
     if (node == null || node.next == null) {
      prev = node;
     } else {
      Node tmp = reverseLinkList(node.next);
      node.next.next = node;
      node.next = null;
      prev = tmp;
     }
     return prev;
     }

    반전 링크 참조:https://www.jb51.net/article/136185.htm
    마지막
    링크 자 체 를 이해 하 는 것 은 어렵 지 않 지만 관련 조작 을 하면 머리 가 아프다.head.next next next next next next next..............................................................
    체인 시 계 를 조작 하려 면 머리 지침 만 알 면 모든 조작 을 할 수 있다.
    1.링크 에 데이터 추가
  • 끝 노드 를 찾 아 옮 겨 다 니 며 삽입 하면 됩 니 다(while(temp.next!=null),순환 을 종료 하면 끝 노드 를 찾 습 니 다
  • 2.링크 옮 겨 다 니 기
  • 첫 번 째 노드(유효 노드)부터 null 이 아니면 출력
  • 3.주어진 위치 에 노드 를 링크 에 삽입 합 니 다.
  • 이 위치 가 효과 가 있 는 지 먼저 판단 한다(링크 길이 의 범위 내 에서)
  • 위 치 를 삽입 하려 는 이전 노드 를 찾 습 니 다.
    이전 노드 의 가리 키 는 방향 을 삽 입 된 노드 에 맡 깁 니 다.
    이전 노드 포인터 영역 은 삽입 하고 자 하 는 노드 를 가리 키 고 있 습 니 다
  • 4.링크 길이 가 져 오기
  • 노드 에 한 번 방문 할 때마다 변수+조작 하면 됩 니 다
  • 5.주어진 위치 에 있 는 노드 삭제
  • 이 위치 가 효과 가 있 는 지 먼저 판단 한다(링크 길이 의 범위 내 에서)
  • 위 치 를 삽입 하려 는 이전 노드 를 찾 습 니 다.
    이전 노드 에서 뒤의 노드 를 가리 키 는 것
  • 6.링크 정렬
  • 거품 알고리즘 을 사용 하여 정렬
  • 7.링크 에서 마지막 k 번 째 노드 를 찾 습 니 다.
  • 두 개의 포인터 p1,p2 를 설정 하여 p2 가 p1 보다 k 개의 노드 를 빠르게 하 는 동시에 뒤로 옮 겨 다 니 며 p2 가 비어 있 으 면 p1 은 꼴찌 k 개의 노드
  • 입 니 다.
    8.링크 중복 데이터 삭제
  • 조작 은 거품 과 정렬 차이 가 많 지 않 습 니 다.똑 같 으 면 삭제 할 수 있 습 니 다~
  • 9.링크 의 중간 노드 조회
  • 이 알고리즘 도 재 미 있 습 니 다.하 나 는 매번 한 걸음 씩 걷 고 하 나 는 두 걸음 씩 걷 고 두 걸음 씩 걷 는 것 이 끝 난 다음 에 한 걸음 걷 는 지침 입 니 다.바로 중간 노드
  • 입 니 다.
    10.재 귀 는 끝 에서 끝까지 단일 체인 표를 출력 한다.
  • 아래 에 데이터 가 있 으 면 아래로 찾 아 보 세 요.재 귀 는 마지막 에서 앞으로 넘 어 집 니 다.
  • 11.반전 링크
  • 재 귀 와 비 재 귀 두 가지 방식 이 있 는데 저 는 매우 어렵다 고 생각 합 니 다.제 가 드 린 링크 에서 찾 아 보 세 요~
  • PS:모든 사람의 실현 이 다 르 기 때문에 작은 디 테 일 은 변동 이 있 을 수 있 고 고정된 쓰기 도 없 으 며 대응 하 는 기능 을 실현 할 수 있 습 니 다~
    총결산
    이상 은 이 글 의 전체 내용 입 니 다.본 논문 의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 참고 학습 가치 가 있 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 댓 글 을 남 겨 주 셔 서 저희 에 대한 지지 에 감 사 드 립 니 다.
    참고 자료:
  • http://www.cnblogs.com/whgk/p/6589920.html
  • https://www.cnblogs.com/bywallance/p/6726251.html
  • 좋은 웹페이지 즐겨찾기