Insertion d'un nouveau nœud dans une structure de données de liste chaînée
L'insertion d'un nouveau nœud dans la liste liée peut faire 3 façons.
- Au début de la liste liée
- Au milieu de la liste liée
- À la fin de la liste liée
Avant de commencer, vous devez connaître la liste liée et comment la créer.
1. Au début de la liste liée
package in.eyehunt.data.struc; public class LinkedList { Node head; // head of list // Linked list Node. class Node { int data; Node next; // Parameterized constructor Node(int d) { data = d; next = null; } } // method to add new node in start void push(int n) { //create new node Node newNode = new Node(n); // next node is head newNode.next = head; // move had point to new node head = newNode; } void printAllNodes() { Node node = head; while (node != null) { System.out.print("-> "+node.data); node = node.next; } } public static void main(String a[]) { //create a simple linked list with 4 nodes LinkedList linkedList = new LinkedList(); linkedList.push(1); linkedList.push(4); linkedList.push(3); linkedList.push(2); linkedList.printAllNodes(); } }
2. Au milieu de la liste liée
Insérez un nouveau nœud avec des données au milieu de la liste et une liste chaînée contenant n nœuds..
Donc maintenant la condition est :
- Si n est pair, puis insérez le nouveau nœud après le (n/2) ème nœud,
- autrement insérer le nouveau nœud après le (n+1)/ 2ème nœud.
Vous devez lire ce didacticiel pour trouver la longueur des données d'une liste liée pour une meilleure compréhension.
package in.eyehunt.data.struc; public class LinkedList { Node head; // head of list // Linked list Node. class Node { int data; Node next; // Parameterized constructor Node(int d) { data = d; next = null; } } void push(int n) { //create new node Node newNode = new Node(n); // next node is head newNode.next = head; // move had point to new node head = newNode; } void addMiddleNode(int n) { if (head == null) { head = new Node(n); } else { int middleNode = (count() % 2 == 0) ? (count() / 2) : ((count() + 1) / 2); //create new node Node newNode = new Node(n); Node pointerNode = head; int countNodes = 0; while (countNodes != middleNode -1) { pointerNode = pointerNode.next; countNodes ++; } System.out.println("\n Middle node of linked List " + middleNode); System.out.println("\n Middle node data " + pointerNode.data); // adding new node in middle newNode.next = pointerNode.next; pointerNode.next = newNode; printAllNodes(); } } //Returns count of nodes in linked list (iteration) public int count() { int a = 0; Node n = head; while (n != null) { n = n.next; a++; } return a; } void printAllNodes() { Node node = head; while (node != null) { System.out.print("-> " + node.data); node = node.next; } } public static void main(String a[]) { //create a simple linked list with 4 nodes LinkedList linkedList = new LinkedList(); linkedList.push(1); linkedList.push(9); linkedList.push(7); linkedList.push(2); linkedList.printAllNodes(); linkedList.addMiddleNode(3); } }
3. Ajouter un nœud dans la liste liée Dernier
package in.eyehunt.data.struc; public class LinkedList { Node head; // head of list // Linked list Node. class Node { int data; Node next; // Parameterized constructor Node(int d) { data = d; next = null; } } void append(int n) { // create new node Node newNode = new Node(n); // if head is null add new head if (head == null) { head = new Node(n); return; } //traverse till the last node Node last = head; while (last.next != null) { last = last.next; } //Add the new node of last node last.next = newNode; return; } void printAllNodes() { Node node = head; while (node != null) { System.out.print("-> "+node.data); node = node.next; } } public static void main(String a[]) { //create a simple linked list with 4 nodes LinkedList linkedList = new LinkedList(); linkedList.append(1); linkedList.append(4); linkedList.append(3); linkedList.append(2); linkedList.printAllNodes(); } }