Other data structure articles

The previous chapter introduced some operations of one-way lists. This chapter introduces two-way lists of data structures

What is a bidirectional list

A bidirectional linked list, also known as a doubly linked list, is a type of linked list in which each data node has two Pointers pointing to the direct successor and direct precursor respectively. So, starting from any node in a bidirectional linked list, you can easily access its predecessors and successors. In general, we construct bidirectional circular lists.

Baidu encyclopedia

Auxiliary image:

Let’s look at the node class (HeroNode2):

  • Id is followed by id to sort the bidirectional list
  • Name is an arbitrary parameter
  • Next stores the next element (the last next is null)
  • The pre saves the previous element (the pre of the first element is null)

Add elements

Analysis:

  • The default is to add the element to the last position, so you only need to iterate through all the data in the list. When next is null, it means that you are currently in the last position

Let’s start with the code:

public class DoubleLinkedList {

    // Identifies the first node location, does not store elements
    private HeroNode2 head = new HeroNode2(0."");

    public void add(HeroNode2 heroNode2) {
        HeroNode2 temp = head;

        while(temp.next ! =null) {
            // The list moves back
            temp = temp.next;
        }

        // Add the last elementtemp.next = heroNode2; heroNode2.pre = temp; }}Copy the code

Use:

        doubleLinkedList.add(new HeroNode2(1.Bone fairy));
        doubleLinkedList.add(new HeroNode2(2."Li Yunlong"));
        doubleLinkedList.add(new HeroNode2(3."Sung river"));
        doubleLinkedList.add(new HeroNode2(4."Sun Wukong"));
        doubleLinkedList.add(new HeroNode2(5."Liu Guoqiang"));
        
        System.out.println("\n The original data is :");
        doubleLinkedList.show();
Copy the code

The running results are as follows:

The original data is HeroNode2{id=1, name='Ghost of Bones'}
HeroNode2{id=2, name='Li Yunlong'}
HeroNode2{id=3, name='sung river'}
HeroNode2{id=4, name=Sun Wukong}
HeroNode2{id=5, name='Liu Guoqiang'}
Copy the code

Auxiliary graph:

Show display method:

public void show(a) {
        if (head.next == null) {
            System.out.println("List elements unll cannot be printed");
            return;
        }

        HeroNode2 temp = head;
        while(temp.next ! =null) {
            / / ward temptemp = temp.next; System.out.println(temp); }}Copy the code

This display method is easy to understand, loop to determine if tempNext is null,! =null and print all the time

Remove elements

Analysis:

The idea of deleting an element is the same as that of a single linked list. You need to pass in the id of the deleted element to determine whether it exists in the list, and then delete it

Let’s look at the code:

  // Delete elements by id
    public void remove(int id) {
        if (head.next == null) {
            System.out.println("Linked list is null and cannot be deleted");
            return;
        }

        // Start the loop from the first element
        HeroNode2 temp = head.next;

        If temp. Id == id indicates that the linked list has the same element, it can be deleted
        boolean flag = false;

        while(temp ! =null) {
            if (temp.id == id) {
                flag = true;
                break;
            }
            / / ward temp
            temp = temp.next;
        }

        if (flag) {
            temp.pre.next = temp.next;

            if(temp.next ! =null) { temp.next.pre = temp.pre; }}else {
            System.out.println("No element found."+ id); }}Copy the code

Use:

        doubleLinkedList.remove(2);
        doubleLinkedList.remove(5);
        System.out.println("After deleting elements, the data is :");
        doubleLinkedList.show();
Copy the code

The final result is:

HeroNode2{id=1, name='Ghost of Bones'}
HeroNode2{id=3, name='sung river'}
HeroNode2{id=4, name=Sun Wukong}
Copy the code

Auxiliary graph:

Replace the element

Analysis:

The idea of replacing an element is the same as that of a singly linked list. You pass in an element to be replaced and then replace the element

The first step is to determine whether the id passed in exists in the linked list. If it exists, it can be replaced. If it does not exist, it cannot be replaced

Take a look at the code:

// Replace elements
    public void upData(HeroNode2 heroNode2) {
        if (head.next == null) {
            System.out.println("Cannot be replaced. Data is empty.");
            return;
        }

        HeroNode2 temp = head.next;

        boolean flag = false;

        while(temp ! =null) {
            if (temp.id == heroNode2.id) {
                flag = true;
                break;
            }
            / / ward temp
            temp = temp.next;
        }

        if (flag) {
            temp.name = heroNode2.name;
            temp.id = heroNode2.id;

        } else {
            System.out.println("Not in the list." + heroNode2.name + "Elements"); }}Copy the code

Use:

        System.out.println("\n The original data is :");
        doubleLinkedList.show();

        HeroNode2 newHero = new HeroNode2(1."李逵");
        doubleLinkedList.upData(newHero);
        System.out.println("\n Replace elements with :");
        doubleLinkedList.show();
Copy the code

The final result is:

The original data is HeroNode2{id=1, name='Ghost of Bones'}
HeroNode2{id=2, name='Li Yunlong'}
HeroNode2{id=3, name='sung river'}
HeroNode2{id=4, name=Sun Wukong}
HeroNode2{id=5, name='Liu Guoqiang'} HeroNode2{id=1, name='李逵'}
HeroNode2{id=2, name='Li Yunlong'}
HeroNode2{id=3, name='sung river'}
HeroNode2{id=4, name=Sun Wukong}
HeroNode2{id=5, name='Liu Guoqiang'}
Copy the code

Auxiliary graph:

Sort by ID

Analysis:

If head. Next. Id > heronode2.id (the id passed in) then the loop is terminated and the list is inserted into the current node

Let’s start with the code:

 // Sort by id
    public void addId(HeroNode2 heroNode2) {
        HeroNode2 temp = head;

        while(temp.next ! =null) {
            if (temp.next.id > heroNode2.id) {
                break;
            }
            temp = temp.next;
        }

        heroNode2.next = temp.next;

        if(temp.next ! =null) {
            temp.next.pre = heroNode2;
        }

        heroNode2.pre = temp;

        temp.next = heroNode2;
    }
Copy the code

Use:

        doubleLinkedList.addId(new HeroNode2(5."Liu Guoqiang"));
        doubleLinkedList.addId(new HeroNode2(1.Bone fairy));
        doubleLinkedList.addId(new HeroNode2(4."Sun Wukong"));
        doubleLinkedList.addId(new HeroNode2(2."Li Yunlong"));
        doubleLinkedList.addId(new HeroNode2(3."Sung river"));
        
        System.out.println("\n The original data is :");
        doubleLinkedList.show();
Copy the code

The running results are as follows:

The original data is HeroNode2{id=1, name='Ghost of Bones'}
HeroNode2{id=2, name='Li Yunlong'}
HeroNode2{id=3, name='sung river'}
HeroNode2{id=4, name=Sun Wukong}
HeroNode2{id=5, name='Liu Guoqiang'}
Copy the code

Illustration:

The final result is:

You may be a little confused, data structure is such, a little difference can cause a big reaction, although this is only a little code, I also summarized several days.

Personal advice: if you want to learn bidirectional linked list before single linked list add/delete/change/add according to ID must be able to write! One-way linked lists two-way linked lists are easy to understand

And then there are the data structures, which can only be understood but not spoken!

Come on!

The complete code

What do you like?

Data structures and algorithms directory

Original is not easy, your praise is the biggest support for me!