Java >> Tutoriel Java >  >> Tag >> new

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.

  1. Au début de la liste liée
  2. Au milieu de la liste liée
  3. À 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();
    }
}

Balise Java