Implementierungscode für die Operation einer verknüpften Liste mit Java-Datenstruktur

Eine verknüpfte Liste ist eine komplexe Datenstruktur. Die Wechselbeziehung zwischen ihren Daten unterteilt die verknüpfte Liste in drei Typen: einfach verknüpfte Liste, zirkulär verknüpfte Liste und doppelt verknüpfte Liste, die im Folgenden einzeln vorgestellt werden. Verknüpfte Listen bilden die Grundlage in Datenstrukturen und sind auch wichtige Wissenspunkte. Hier werden wir über die Implementierung verknüpfter Listen in Java sprechen,

JAVA-verknüpfte Listenoperationen: einfach verknüpfte Listen und doppelt verknüpfte Listen

Sprechen Sie hauptsächlich über die folgenden Punkte:

1. Einführung in verknüpfte Listen

2. Prinzipien und Notwendigkeit der Implementierung verknüpfter Listen

3

4. Beispiele für doppelt verknüpfte Tabellen

1. Einführung in verknüpfte Listen

Verknüpfte Listen sind eine häufig verwendete Datenstruktur. Sie sind bequemer für die Abfrage und werden in vielen Computersprachen verwendet. Verknüpfte Listen verfügen über verschiedene Kategorien. Der Artikel analysiert einfach verknüpfte Listen und doppelt verknüpfte Listen. Die Daten in der verknüpften Liste sind wie eine in Reihe geschaltete Kette und der Zugriff auf die Daten ist einfach.

2. Prinzip und Notwendigkeit der Implementierung verknüpfter Listen

Hier analysieren wir nur einfach verknüpfte Listen und doppelt verknüpfte Listen. Der Implementierungsprozess verknüpfter Listen ist etwas kompliziert, bringt jedoch viele Vorteile mit sich. Jetzt, da das Zeitalter des Online-Shoppings angebrochen ist, verpacken Händler ihre Waren normalerweise in Kartons und vermerken beim Expressversand die Adressinformationen. Das Kurierunternehmen kann die Informationen auf dem Karton verwenden, um den Käufer zu finden, und die Waren kommen unversehrt an. Ohne den Schutz des Kartons kann es zu Transportschäden an der Ware kommen. Die verknüpfte Liste ist wie die Box mit den darauf geschriebenen Adressinformationen, die nicht nur die Produktinformationen schützt, sondern auch die Logistikinformationen schreibt. In der verknüpften Liste gibt es einen HEAD-Knoten, ähnlich einer „Lokomotive“. Solange der entsprechende HEAD-Knoten gefunden wird, kann die verknüpfte Liste bedient werden. In dieser Analyse dient der HEAD-Knoten nur als Datenheader und speichert keine gültigen Daten.

Das Implementierungsprinzip einer einfach verknüpften Liste ist wie in der Abbildung dargestellt:

Das Implementierungsprinzip einer doppelt verknüpften Liste:

Drei, Beispiel für eine einzelne verknüpfte Liste

ICommOperate8742468051c85b06f0a0af9e3e506b5c Schnittstellenoperationsklasse:

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

Einfach verknüpfter Listenknoten:

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

Einzelverbindungsoperationsklasse:

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

; Schnittstellenoperationsklasse:

Doppelt verknüpfter Listenknoten:

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

Doppelt verknüpfte Listenimplementierungsklasse:

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

Vielen Dank fürs Lesen, ich hoffe, es kann Ihnen helfen, vielen Dank für Ihre Unterstützung dieser Website!

Weitere Artikel zum Implementierungscode für Java-Datenstruktur-Linked-List-Operationen finden Sie auf der chinesischen PHP-Website!

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