지역 사회 배우다 도구 라이브러리 여가
찾다
한국어
집 > Java > java지도 시간 > Java 데이터 구조 연결 목록 작업 구현 코드

Java 데이터 구조 연결 목록 작업 구현 코드

高洛峰
풀어 주다： 2017-01-16 15:33:58
원래의
1374명이 탐색했습니다.

연결 리스트는 데이터 간의 상호 관계가 복잡한 데이터 구조로, 연결 리스트를 단일 연결 리스트, 순환 연결 리스트, 이중 연결 리스트의 세 가지 유형으로 구분하는데, 이에 대해 하나씩 소개하겠습니다. 연결 목록은 데이터 구조의 기초이자 중요한 지식 포인트이기도 합니다. 여기서는 Java의 연결 목록 구현에 대해 설명합니다.

JAVA 연결 목록 작업: 단일 연결 목록 및 이중 연결 목록

다음 사항을 주로 이야기하세요.

1. 연결 리스트 소개

2. 연결 리스트 구현의 원리와 필요성

3.

4. 이중 연결 테이블의 예

1. 연결 목록 소개

연결 목록은 일반적으로 사용되는 데이터 구조이지만 저장하기가 더 복잡합니다. 연결 목록에는 다양한 범주가 있으며, 이 기사에서는 단일 연결 목록과 이중 연결 목록을 분석합니다. 연결리스트의 데이터는 체인으로 직렬로 연결되어 있는 것과 같으며, 데이터에 쉽게 접근할 수 있습니다.

2. 연결리스트 구현의 원리와 필요성

여기서는 단일 연결리스트와 이중 연결리스트만 분석합니다. 연결 목록의 구현 과정은 다소 복잡하지만 많은 이점을 제공합니다. 예를 들어, 온라인 쇼핑 시대가 도래한 지금, 가맹점에서는 보통 택배로 물건을 상자에 포장하고 택배회사가 상자에 적힌 정보를 이용해 구매자를 찾을 수 있고, 물건은 그대로 도착한다. 박스를 보호하지 않은 경우, 배송 중 상품이 손상될 수 있습니다. 링크드 리스트는 주소 정보가 적힌 상자와 같아서 상품 정보를 보호할 뿐만 아니라 물류 정보도 적는다. Linked List에는 "Locomotive"와 마찬가지로 HEAD 노드가 존재하며, 해당 HEAD 노드를 찾으면 Linked List를 운용할 수 있다. 본 분석에서 HEAD 노드는 데이터 헤더 역할만 하며 유효한 데이터를 저장하지 않습니다.

단일 연결 리스트의 구현 원리는 그림과 같습니다.

Java 数据结构链表操作实现代码

이중 연결 리스트의 구현 원리는

Java 数据结构链表操作实现代码

세 개의 단일 연결 목록 예

ICommOperate 인터페이스 작업 클래스: 

package LinkListTest;
import java.util.Map;
public interface ICommOperate<T> {
   
  public boolean insertNode(T node) ;
  public boolean insertPosNode(int pos, T node) ;
  public boolean deleteNode(int pos) ;
  public boolean updateNode(int pos, Map<String, Object> map) ;
  public T getNode(int pos, Map<String, Object> map) ;
  public void printLink() ;
}
로그인 후 복사

단일 연결 목록 노드: 

package LinkListTest;
// 单连表节点
public class SNode {
  private String data;
  private SNode nextNode;
  public SNode() {
  }
  public SNode(String data) {
    this.data = data;
    this.nextNode = new SNode();
  }
   
  public String getData() {
    return data;
  }
  public void setData(String data) {
    this.data = data;
  }
  public SNode getNextNode() {
    return nextNode;
  }
  public void setNextNode(SNode nextNode) {
    this.nextNode = nextNode;
  }
  @Override
  public String toString() {
    return "SNode [data=" + data + "]";
  }
}
로그인 후 복사

단일 링크 연산 클래스: 

package LinkListTest;
import java.util.HashMap;
import java.util.Map;
public class SingleLinkList implements ICommOperate<SNode>{
  private SNode head = new SNode("HEAD") ; // 公共头指针，声明之后不变
  private int size = 0 ;
  public int getSize() {
    return this.size;
  }
 
  /*
   * 链表插入，每次往末端插入
   * */
  @Override
  public boolean insertNode(SNode node) {
    boolean flag = false ;
    SNode current = this.head ;
    if( this.size==0 ){ // 空链表
      this.head.setNextNode(node) ;
      node.setNextNode(null) ;
    }else{        // 链表内节点
      while( current.getNextNode()!=null ){
        current = current.getNextNode() ;
      }
      current.setNextNode(node) ;
      node.setNextNode(null) ;
    }
    this.size++ ;
    flag = true ;
     
    return flag;
  }
 
  /*
   * 插入链表指定位置pos，从1开始,而pos大于size则插入链表末端
   * */
  @Override
  public boolean insertPosNode(int pos, SNode node){
    boolean flag = true;
    SNode current = this.head.getNextNode() ;
     
    if( this.size==0 ){          // 空链表
      this.head.setNextNode(node) ;
      node.setNextNode(null) ;
      this.size++ ;
    }else if( this.size<pos ){      // pos位置大于链表长度，插入末端
      insertNode(node) ;
    }else if( pos>0 && pos<=this.size) { // 链表内节点
      // 1、找到要插入pos位置节点和前节点
      int find = 0;
      SNode preNode = this.head; // 前节点
      SNode currentNode = current; // 当前节点
      while( find<pos-1 && currentNode.getNextNode()!=null ){
        preNode = current ;          // 前节点后移
        currentNode = currentNode.getNextNode() ; // 当前节点后移
        find++ ;
      }
//      System.out.println(preNode);
//      System.out.println(currentNode);
      // 2、插入节点
      preNode.setNextNode(node);
      node.setNextNode(currentNode);
      this.size++ ;
      System.out.println("节点已经插入链表中");
    }else{
      System.out.println("位置信息错误");
      flag = false ;
    }
     
    return flag;
  }
   
  /*
   * 指定链表的节点pos，删除对应节点。方式：找到要删除节点的前后节点，进行删除。从1开始
   * */
  @Override
  public boolean deleteNode(int pos) {
    boolean flag = false;
    SNode current = this.head.getNextNode() ;
    if( pos<=0 || pos>this.size || current==null ){
      System.out.println("位置信息错误或链表无信息");
    }else{
      // 1、找到要删除节点的前后节点
      int find = 0;
      SNode preNode = this.head; // 前节点
      SNode nextNode = current.getNextNode(); // 后节点
      while( find<pos-1 && nextNode.getNextNode()!=null ){
        preNode = current ;          // 前节点后移
        nextNode = nextNode.getNextNode() ; // 后节点后移
        find++ ;
      }
//      System.out.println(preNode);
//      System.out.println(nextNode);
       
      // 2、删除节点
      preNode.setNextNode(nextNode);
      System.gc();
      this.size-- ;
      flag = true ;
    }
     
    return flag;
  }
 
  /*
   * 指定链表的节点pos，修改对应节点。 从1开始
   * */
  @Override
  public boolean updateNode(int pos, Map<String, Object> map) {
    boolean flag = false ;
    SNode node = getNode(pos, map); // 获得相应位置pos的节点
    if( node!=null ){
      String data = (String) map.get("data") ;
      node.setData(data);
      flag = true ;
    }
    return flag;
  }
 
  /*
   * 找到指定链表的节点pos，从1开始
   * */
  @Override
  public SNode getNode(int pos, Map<String, Object> map) {
    SNode current = this.head.getNextNode() ;
    if( pos<=0 || pos>this.size || current==null ){
      System.out.println("位置信息错误或链表不存在");
      return null;
    }
    int find = 0 ;
    while( find<pos-1 && current!=null ){
      current = current.getNextNode() ;
      find++ ;
    }
    return current;
  }
 
  /*
   * 打印链表
   * */
  @Override
  public void printLink() {
    int length = this.size ;
    if( length==0 ){
      System.out.println("链表为空！");
      return ;
    }
    SNode current = this.head.getNextNode() ;
    int find = 0 ;
    System.out.println("总共有节点数: " + length +" 个");
    while( current!=null ){
      System.out.println("第 " + (++find) + " 个节点 ：" + current);
      current=current.getNextNode() ;
    }
  }
   
  public static void main(String[] args) {
    SingleLinkList sll = new SingleLinkList() ;
    SNode node1 = new SNode("节点1");
    SNode node2 = new SNode("节点2");
    SNode node3 = new SNode("节点3");
    SNode node4 = new SNode("节点4");
    SNode node5 = new SNode("节点5");
    SNode node6 = new SNode("插入指定位置");
    sll.insertPosNode(sll.getSize()+1, node1) ;
    sll.insertPosNode(sll.getSize()+1, node2) ;
    sll.insertPosNode(sll.getSize()+1, node3) ;
    sll.insertPosNode(sll.getSize()+1, node4) ;
    sll.insertPosNode(sll.getSize()+1, node5) ;
     
//    sll.insertNode(node1);
//    sll.insertNode(node2);
//    sll.insertNode(node3);
//    sll.insertNode(node4);
//    sll.insertNode(node5);
     
    System.out.println("*******************输出链表*******************");
    sll.printLink();
     
    System.out.println("*******************获得指定链表节点*******************");
    int pos = 2 ;
    System.out.println("获取链表第 "+pos+" 个位置数据 ："+sll.getNode(pos, null));
     
    System.out.println("*******************向链表指定位置插入节点*******************");
    int pos1 = 2 ;
    System.out.println("将数据插入第 "+pos1+" 个节点：");
    sll.insertPosNode(pos1, node6) ;
    sll.printLink();
     
    System.out.println("*******************删除链表指定位置节点*******************");
    int pos2 = 2 ;
    System.out.println("删除第 "+pos2+" 个节点：");
    sll.deleteNode(pos2) ;
    sll.printLink();
     
    System.out.println("*******************修改链表指定位置节点*******************");
    int pos3 = 2 ;
    System.out.println("修改第 "+pos3+" 个节点：");
    Map<String, Object> map = new HashMap<>() ;
    map.put("data", "this is a test") ;
    sll.updateNode(pos3, map) ;
    sll.printLink();
  }
}
로그인 후 복사

이중 링크 테이블 예시

ICommOperate 인터페이스 작업 클래스:

package LinkListTest;
import java.util.Map;
public interface ICommOperate<T> { 
  public boolean insertNode(T node) ;
  public boolean insertPosNode(int pos, T node) ;
  public boolean deleteNode(int pos) ;
  public boolean updateNode(int pos, Map<String, Object> map) ;
  public T getNode(int pos, Map<String, Object> map) ;
  public void printLink() ;
}
로그인 후 복사

이중 연결 목록 노드: 

package LinkListTest;
// 双连表节点
public class DNode {
  private DNode priorNode;
  private String data;
  private DNode nextNode;
   
  public DNode(){
  }
  public DNode(String data) {
    this.priorNode = new DNode() ;
    this.data = data ;
    this.nextNode = new DNode() ;
  }
 
  public DNode getPriorNode() {
    return priorNode;
  }
  public void setPriorNode(DNode priorNode) {
    this.priorNode = priorNode;
  }
 
  public String getData() {
    return data;
  }
  public void setData(String data) {
    this.data = data;
  }
 
  public DNode getNextNode() {
    return nextNode;
  }
  public void setNextNode(DNode nextNode) {
    this.nextNode = nextNode;
  }
 
  @Override
  public String toString() {
    return "DNode [data=" + data + "]";
  } 
}
로그인 후 복사

이중 연결 목록 구현 class: 

package LinkListTest;
import java.util.HashMap;
import java.util.Map;
public class DoubleLinkList implements ICommOperate<DNode>{
  private DNode head = new DNode("HEAD");
  private int size = 0 ;
  public int getSize() {
    return this.size;
  }
   
  /*
   * 链表插入，每次往末端插入
   * */
  @Override
  public boolean insertNode(DNode node) {
    boolean flag = false;
     
    DNode current = this.head ;
    if( this.size==0 ){ // 空链表
      this.head.setNextNode(node) ;
      node.setPriorNode(this.head);
      node.setNextNode(null) ;
    }else{        // 链表内节点
      while( current.getNextNode()!=null ){
        current = current.getNextNode() ;
      }
      current.setNextNode(node);
      node.setNextNode(null);
      node.setPriorNode(current);
    }
    this.size++ ;
    flag = true ;
   
    return flag;
  }
   
  /*
   * 插入链表指定位置pos，从1开始,而pos大于size则插入链表末端
   * */
  @Override
  public boolean insertPosNode(int pos, DNode node) {
    boolean flag = true;
     
    DNode current = this.head.getNextNode() ;
    if( this.size==0){             // 链表为空
      this.head.setNextNode(node) ;
      node.setNextNode(null) ;
      node.setPriorNode(this.head);
      this.size++ ;
    }else if( pos>this.size ){         // pos位置大于链表长度，插入末端
      insertNode(node) ;
    }else if( pos>0 && pos<=this.size ){  // 链表内节点
      // 1、找到要插入位置pos节点，插入pos节点当前位置
      int find = 0;
      while( find<pos-1 && current.getNextNode()!=null ){
        current = current.getNextNode() ;
        find++ ;
      }
      // 2、插入节点
      if( current.getNextNode()==null ){ // 尾节点
        node.setPriorNode(current);
        node.setNextNode(null);
        current.setNextNode(node);
      } else if( current.getNextNode()!=null ) { //中间节点
        node.setPriorNode(current.getPriorNode());
        node.setNextNode(current);
        current.getPriorNode().setNextNode(node);
        current.setPriorNode(node);
      }
      this.size++ ;
    }else{
      System.out.println("位置信息错误");
      flag = false ;
    }
     
    return flag;
  }
   
  /*
   * 指定链表的节点pos，删除对应节点，从1开始
   * */
  @Override
  public boolean deleteNode(int pos) {
    boolean flag = false;
    DNode current = this.head.getNextNode() ;
    if( pos<=0 || pos>this.size || current==null ){
      System.out.println("位置信息错误或链表不存在");
    }else{
      // 1、找到要删除位置pos节点
      int find = 0;
      while( find<pos-1 && current.getNextNode()!=null ){
        current = current.getNextNode() ;
        find++ ;
      }
      // 2、删除节点
      if( current.getNextNode()==null ){ // 尾节点
        current.getPriorNode().setNextNode(null) ;
      } else if( current.getNextNode()!=null ) { //中间节点
        current.getPriorNode().setNextNode(current.getNextNode()) ;
        current.getNextNode().setPriorNode(current.getPriorNode()) ;
      }
      System.gc();
      this.size-- ;
      flag = true ;
    }
    return flag;
  }
 
  /*
   * 指定链表的节点pos，修改对应节点。 从1开始
   * */
  @Override
  public boolean updateNode(int pos, Map<String, Object> map) {
    boolean flag = false ;
    DNode node = getNode(pos, map);
    if( node!=null ){
      String data = (String) map.get("data") ;
      node.setData(data);
      flag = true ;
    }
    return flag;
  }
   
  /*
   * 找到指定链表的节点pos，从1开始
   * */
  @Override
  public DNode getNode(int pos, Map<String, Object> map) {
    DNode current = this.head.getNextNode() ;
    if( pos<=0 || pos>this.size || current==null ){
      System.out.println("位置信息错误或链表不存在");
      return null;
    }
    int find = 0 ;
    while( find<pos-1 && current!=null ){
      current = current.getNextNode() ;
      find++ ;
    }
    return current;
  }
   
  /*
   * 打印链表
   * */
  @Override
  public void printLink() {
    int length = this.size ;
    if( length==0 ){
      System.out.println("链表为空！");
      return ;
    }
    DNode current = this.head.getNextNode() ;
    int find = 0 ;
    System.out.println("总共有节点数: " + length +" 个");
    while( current!=null ){
      System.out.println("第 " + (++find) + " 个节点 ：" + current);
      current=current.getNextNode() ;
    }
  }
   
  public static void main(String[] args) {
    DoubleLinkList dll = new DoubleLinkList() ;
    DNode node1 = new DNode("节点1");
    DNode node2 = new DNode("节点2");
    DNode node3 = new DNode("节点3");
    DNode node4 = new DNode("节点4");
    DNode node5 = new DNode("节点5");
    DNode node6 = new DNode("插入指定位置");
    dll.insertPosNode(10, node1) ;
    dll.insertPosNode(10, node2) ;
    dll.insertPosNode(10, node3) ;
    dll.insertPosNode(10, node4) ;
    dll.insertPosNode(10, node5) ;
//    dll.insertNode(node1);
//    dll.insertNode(node2);
//    dll.insertNode(node3);
//    dll.insertNode(node4);
//    dll.insertNode(node5);
     
    System.out.println("*******************输出链表*******************");
    dll.printLink();
     
    System.out.println("*******************获得指定链表节点*******************");
    int pos = 2 ;
    System.out.println("获取链表第 "+pos+" 个位置数据 ："+dll.getNode(pos, null));
     
    System.out.println("*******************向链表指定位置插入节点*******************");
    int pos1 = 2 ;
    System.out.println("将数据插入第"+pos1+"个节点：");
    dll.insertPosNode(pos1, node6) ;
    dll.printLink();
     
    System.out.println("*******************删除链表指定位置节点*******************");
    int pos2 = 7 ;
    System.out.println("删除第"+pos2+"个节点：");
    dll.deleteNode(pos2) ;
    dll.printLink();
     
    System.out.println("*******************修改链表指定位置节点*******************");
    int pos3 = 2 ;
    System.out.println("修改第"+pos3+"个节点：");
    Map<String, Object> map = new HashMap<>() ;
    map.put("data", "this is a test") ;
    dll.updateNode(pos3, map) ;
    dll.printLink();
  }
}
로그인 후 복사

읽어주셔서 감사합니다. 모두에게 도움이 되기를 바랍니다. 이 사이트를 지원해 주셔서 감사합니다!

더 많은 Java 데이터 구조 연결 목록 연산 구현 코드 관련 기사를 보려면 PHP 중국어 웹사이트를 주목하세요!

관련 라벨：
Java 数据结构 链表
원천：php.cn
이전 기사：Android 애플리케이션에 WeChat 공유를 추가하는 간단한 방법 다음 기사：숫자 정렬 예제를 구현하기 위한 Java 데이터 구조 및 알고리즘 삽입 알고리즘
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
최신 이슈
MySQL SQL 쿼리를 사용하여 다른 테이블의 필드 합계를 계산합니다. 다음과 같은 스키마가 있습니다. "user_id" 및 "username" 속성이 있는 사용자 테이블과 "custome...
에서 2024-04-06 19:39:29
0
1
441
MySQL: "<여기 변수 또는 하위 쿼리>로...에서 텍스트 선택" 다음 데이터가 포함된 다음 테이블이 있습니다. id 텍스트 언어 1 독일어 텍스트 독일어 2 영어 텍스트 영어 내가 원하는 것은 다음 형식의 결과를 얻는 것입니다...
에서 2024-04-06 19:25:54
0
2
529
MySQL에서 그룹화하고 계산하는 방법은 무엇입니까? 친구에게 보낸 삭제되지 않은 메시지의 총 개수를 추출하는 쿼리를 작성하려고 합니다. 다음은 테이블 구조의 스크린샷입니다. 제가 달성하려는 출력은 다음과 같습니다....
에서 2024-04-06 18:30:17
0
1
353
**오류 유형: 'NoneType' 개체를 반복할 수 없습니다** SSH 터널을 사용하여 MySQL 데이터베이스에 액세스하고 싶습니다. 안타깝게도 이 코드의 아키텍처는 함수가 내 쿼리 형식과 호환되지 않는 것 같기 때문에 내 쿼...
에서 2024-04-06 10:26:38
0
1
378
useState 변수를 다른 구성요소/페이지로 내보내기 나는 조금 붙어 있습니다. 사용자 입력 결과를 다른 구성 요소에서 사용할 수 있는 배열에 넣었습니다. 그러나 다른 구성 요소/페이지에서 "newList&...
에서 2024-04-05 11:30:54
0
1
286
관련 주제
더>
인기 추천
인기 튜토리얼
더>
관련 튜토리얼
인기 추천
최신 강좌
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿