Maison  >  Article  >  Java  >  Introduction et utilisation de la liste à chaînage unique en Java

Introduction et utilisation de la liste à chaînage unique en Java

零下一度
零下一度original
2017-06-25 10:28:031833parcourir

Liste chaînée :
* 1. La liste chaînée peut être une liste ordonnée ou non
* 2. Le contenu de la liste chaînée est généralement stocké en mémoire jusqu'à ce qu'il soit dispersé
* 3. La liste chaînée est composée de nœuds Composition, chaque nœud a la même structure
* 4. Les nœuds sont divisés en domaine de données et domaine de chaîne. Le domaine de données stocke le contenu du nœud et le domaine de chaîne stocke le pointeur du nœud suivant <.>

package myLinkList;

classe publique MyLinkedList {

/**
*Nœud : objet nœud
* Comprend le champ de données data et le champ de lien suivant (pointant vers l'objet nœud suivant)
*/
class Node {
 données T privées;
 nœud privé suivant;
 nœud public ( ){

 }
 //Initialisation du nœud
 public Node(T data,Node next){
  this.data = data; >
en-tête de nœud privé ;//nœud principal de la liste chaînée
queue de nœud privé ;//nœud de queue de la liste chaînée
taille int privée ;//longueur de la liste chaînée (nombre de nœuds)


/**
* Initialisation de la liste chaînée
*/
public MyLinkedList() {//Construction de paramètre vide
header = null;
tailer = null;
}
public MyLinkedList (Données T) {//Construction avec paramètres
 header = new Node(data,null);//Créer un nœud d'en-tête
 tailer = header;
 size++;
}

/**
* Trouver la longueur de la liste chaînée
* @return
*/
public int getSize() {
 return size;
}

/**
* Renvoie les données du nœud avec index index
* @param index index
* @return
*/
public T get( int index ) {
 if(index < 0 || index > size-1)
  throw new IndexOutOfBoundsException("index hors limites");
  return getIndexNode(index).data;
}

public Node getIndexNode(int index){
 if(index < 0 || index > size-1)
  throw new IndexOutOfBoundsException("index hors limites");
Node current = header;
 for(int i = 0;i < size; i++) {
  if(i == index) {
  retour courant;
  }
  courant = courant .next ;
}
return null;
}

/**
* Renvoie la position de l'élément dans la liste chaînée, s'il n'existe pas, renvoie -1
* @param tdata
* @return
*/
public int getIndex(T element) {
if(element == null)
  return -1;
 Node current = header;
 for(int i = 0; i < size; i++) {
  if(current.data == element){
  return i;
}
current = current.next;
}
return -1;
}



/**
* Ajouter un élément
à la fin de la liste chaînée * @param element
*/
public void add(T element) {
 Node n = new Node(element,null);
 if(header == null){
 header = n;
 tailer = header;
}else{
tailer.next = n;
tailer = n;
}
size++;
}

/**
* Ajouter un élément
en tête de la liste chaînée * @param element
* /
public void addAtheader(T element) {
header = new Node(element,header);
if(tailer == null){
tailer = header;
}
size++;
}

/**
* Insérer un élément après la position de l'index
* @param index
* @param element
*/
public void insert(int index,T element) {
 if(index<0 || index>size-1) {
throw new IndexOutOfBoundsException("index hors limites");
}
if(header==null){
add(element ){
  addAtheader(element);
 }else{
   Node current = getIndexNode(index);
    Node insertNode = new Node(element,current.next);
   current.next = insertNode;
   size ++;
  } < new IndexOutOfBoundsException("index hors limites"); Node
  header = header.next;//Pointez le pointeur de tête vers le nœud suivant
  size--;
  return n.data;//Sortez le contenu du nœud d'enregistrement
  }else{//In Supprimer les autres positions
  Node current = getIndexNode(index);//Obtenir le nœud actuel
  Node pre = getIndexNode(index-1);//Get le nœud précédent
  pre.next = current.next;/ /Définir le champ de chaîne du nœud précédent sur null
  size--;
  return current.data;//Renvoyer le champ de données du nœud supprimé node
  }


}
/**
* Supprimer le nœud à n'importe quelle position
* @param index
* @return
*/
public T deleteHeader(){
return deleteNode(0);
}
/**
* Supprimer le nœud principal
* @return
*/
public T deleteTailer() {
return deleteNode(size-1);
}

//Effacer le nœud
public void clear(){
  header = null;
  tailer = null;
  size = 0;
}

/**
* toString();
*/
public String toString(){
  if(size == 0)
    return "[]";
  Node current = header;
  StringBuilder sb = new StringBuilder();
  sb.append(" [");
  while(current.next != null) {
    sb.append(current.data).append("  ");
    current = current.next;
  }
  sb.append(current.data).append("]");
  return sb.toString();
}


public static void main(String[] args) {
  MyLinkedList link = new MyLinkedList<>();
  link.add("header");
  link.add("11");
  link.add("22");
  link .add("33");
  link.addAtheader("newheader");
  link.insert(2, "1.5");;

  System.out.println(link.getIndex ("11"));
  System.out.println(link.getIndex("88"));
  System.out.println(link.get(0));
  System.out. println(link.getSize());
  System.out.println(link.deleteHeader());
  System.out.println(link.deleteTailer());
  System.out.println( link.deleteNode(1));
  System.out.println(link);
  link.clear();
  System.out.println(link);

  }

}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn