This is the second day of my participation in the August More text Challenge. For details, see:August is more challenging

This series of articles is a summary of personal learning, if there are mistakes or questions, welcome to comment!

This paper is the third in the series of relearning data structures. The series of articles are as follows: 1. Time complexity and space complexity of algorithm 2. Relearn data structures – linked lists

The foreword 0.

To learn about data structures, we first need to understand what they contain, and knowing what they contain will help us learn better. Data structure includes linear structure and nonlinear structure.

Linear structure

  • Linear structure as the most commonly used data structure, its characteristics areData elements are one-to-oneThe linear relationship between
  • Linear structure there are two different types of storage structures, namelySequential storage structures (arrays)andChained storage structure (linked list). A linear table stored sequentially is called a sequential tableThe storage elements are contiguous.
  • A linear list of chained storage is called a linked listStorage elements need not be contiguous, the address information of data elements and adjacent elements is stored in the element node.
  • Common linear structures are arrays, lists, queues, and stacks.

Nonlinear structure

Nonlinear structures include two-dimensional array, multidimensional array, generalized table, tree structure and graph structure.

The plan for this series of articles is to start with a linked list with a linear structure.

1. The linked list

1.1. Introduction

A linked list is an ordered list, but its memory structure is as follows:

Summary above:

  • The linked list is stored in the way of nodes. It is chain storage
  • Each node contains the Data field, which stores data, and the Next field, which points to the next node.
  • Figure: Discover that the nodes of a linked list are not necessarily contiguously stored.
  • The linked list is divided into the list with the head node and the list without the head node, according to the actual needs to determine

Linked list is divided into unidirectional linked list and two-way linked list.

1.2. Unidirectional linked list

The logical structure of single linked list (lead node) is shown as follows:

Using the head of the unidirectional linked list – water Enteromorpha leaderboard management to complete the operation of adding, deleting, modifying and checking heroes.

Add and delete

Create a node

class HeroNode{ public int no; Public String name; Public String nickname; Public HeroNode next; Public HeroNode(int no, String name, String nickname) {this.no = no; this.name = name; this.nickname = nickname; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + ''' + ", nickname='" + nickname + ''' + '}'; }}Copy the code

Traverse the nodes

Traversing the list requires creating a secondary node to point to the head node, traversing one node at a time, one position after the secondary node, until the next domain of the current node is empty.

Public void list(){// define a secondary node to traverse the list(the head node is not allowed to move) HeroNode temp = head.next; While (true){if(temp == null){break; } System.out.println(temp); temp = temp.next; }}Copy the code

Add a node

There are two types of adding nodes:

  • Add a node to the end of the list

    To add a node at the end of the list, you need to first traverse the nodes and then add the last node at the end of the list.

    Public void add(HeroNode HeroNode){// define a secondary node for traversing the list. HeroNode temp = head; While (true){// find the last list if(temp. Next == null){break; } temp = temp.next; } // Add to the end of the list temp. Next = heroNode; }Copy the code

  • Add a node where a condition is met (middle)

    Next =temp. Next =temp. Next =temp

    Public void addByOrder(HeroNode HeroNode){// define a secondary node for traversal. HeroNode temp = head; boolean falg = false; While (true){if(temp. Next == null){break; if(temp. } if(temp. Next. No > heronode.no){// find the corresponding position break; }else if(temp.next.no == heroNode.no){ falg = true; break; } temp = temp.next; } if (falg){// system.out. println(" cannot add, current information already exists "); }else {// insert after temp if(temp. Next! =null){ heroNode.next = temp.next; } temp.next = heroNode; }}Copy the code

Modify the node

Modifying a node is equivalent to traversing the linked list and modifying its information after finding the corresponding node.

Public void update(HeroNode HeroNode){if (head.next == null){system.out.println (" the list is empty "); return; } HeroNode temp = head; boolean falg = false; While (true){if (temp==null){// The list has passed through the break; } if(temp.next.no == heroNode.no){ falg = true; break; } temp = temp.next; } // Update the node if (falg){heronode. next = temp.next; temp.next = heroNode; }else{system.out.println (" the node to be updated does not exist "); }}Copy the code

Remove nodes

It’s easy to figure out how to iterate through the deletion nodes. The code is summarized below.

other

List inversion

Ideas:

  • Define three secondary nodes, reverseHead(new list head), cur(current node), next(next node of current node)
  • Walk through the original list and pick up nodes one at a time, placing them at the top of the reverseHead
  • After traversing all of the original linked list, specify the next node of the original node as the first node of the reverseHead.

Public void reverse () {/ / if the current list is empty, or only one node, without having to reverse the if (head. The next = = null | | head. Next, next = = null) {return; } // Define a helper pointer variable HeroNode cur = head.next; HeroNode next = null; HeroNode reverseHead = new HeroNode(0,"",""); while (cur ! =null){ next = cur.next; Next = reversehead. next; reverseHead.next = cur; cur = next; } head.next = reverseHead.next; }Copy the code

Reverse output

Loop through the list, push each node in turn, and then traverse the stack.

Implementation summary

Class SingleLinkedList{private HeroNode head = new HeroNode(0,"",""); @return */ public HeroNode getHead(){return head; Public void add(heroNode heroNode){// define a secondary node, HeroNode temp = head; While (true){// find the last list if(temp. Next == null){break; } temp = temp.next; } // Add to the end of the list temp. Next = heroNode; } /** * add nodes in order (asC) */ public void addByOrder(HeroNode HeroNode){// define a secondary node HeroNode temp = head; boolean falg = false; While (true){if(temp. Next == null){break; if(temp. } if(temp. Next. No > heronode.no){// find the corresponding position break; }else if(temp.next.no == heroNode.no){ falg = true; break; } temp = temp.next; } if (falg){// system.out. println(" cannot add, current information already exists "); }else {// insert heronode. next = temp. Next; // insert heronode. next = temp. temp.next = heroNode; }} /** * update @param heroNode */ public void update(heroNode heroNode){if (head.next == null){ System.out.println(" list is empty "); return; } HeroNode temp = head; boolean falg = false; While (true){if (temp==null){// The list has passed through the break; } if(temp.next.no == heroNode.no){ falg = true; break; } temp = temp.next; } // Update the node if (falg){heronode. next = temp.next; temp.next = heroNode; }else{system.out.println (" the node to be updated does not exist "); Public void delete(int no){// define a secondary node for HeroNode temp = head; // define a secondary node for HeroNode temp = head; boolean falg = false; While (true){if(temp == null){break; If (temp.next. No == no){falg = true; break; } temp = temp.next; } // Delete the corresponding node if (falg){temp.next = temp.next; }else{system.out.println (" the node to be deleted does not exist "); }} public int getLength(){// define a secondary node HeroNode temp = head.next; int length = 0; while (true){ if(temp == null){ break; } length++; temp = temp.next; } return length; } @param k * @return */ public HeroNode findLastIndexNode(int k){int length = getLength(); if(k <= 0 || k>length){ return null; } HeroNode cur = head.next; int index = 0; while (cur! =null){ if(length-index == k){ break; } index ++; cur = cur.next; } return cur; Public void reverse(){// If the current list is empty or has only one node, Don't need to reverse the if (head. Next = = null | | head. Next. Next = = null) {return; } // Define a helper pointer variable HeroNode cur = head.next; HeroNode next = null; HeroNode reverseHead = new HeroNode(0,"",""); while (cur ! =null){ next = cur.next; Next = reversehead. next; reverseHead.next = cur; cur = next; } head.next = reverseHead.next; Public void reversePrint(){if (head.next == null){return; } Stack<HeroNode> stack = new Stack<HeroNode>(); // Define a secondary node HeroNode cur = head.next; while (cur ! = null){ stack.push(cur); cur = cur.next; } while (stack.size() > 0){ System.out.println(stack.pop()); Public void list(){HeroNode temp = head.next;} /** * Display list */ public void list(){HeroNode temp = head.next; While (true){if(temp == null){break; } System.out.println(temp); temp = temp.next; }}}Copy the code

test

Public class SingleLinkedListDemo {public static void main(String[] args) {HeroNode hero1 = new HeroNode(1, "song Jiang "," timely rain "); HeroNode hero2 = new HeroNode(2, hero2); HeroNode hero2 = new HeroNode(2, hero2); HeroNode hero3 = new HeroNode(3, "hero "," hero "); HeroNode hero4 = new HeroNode(4, ""); HeroNode hero4 = new HeroNode(4," "); SingleLinkedList = new SingleLinkedList(); // singlelinkedList.add (hero1); // singleLinkedList.add(hero4); // singleLinkedList.add(hero2); // singleLinkedList.add(hero3); singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero4); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero3); System.out.println(" traversing the list ~~"); singleLinkedList.list(); HeroNode newHeroNode = newHeroNode (2, ""); HeroNode newHeroNode = newHeroNode (2," "); singleLinkedList.update(newHeroNode); System.out.println(" after modification ~~"); singleLinkedList.list(); System.out.println(" ~~~~ after deletion "); singleLinkedList.delete(3); singleLinkedList.list(); System.out.println(" after the list is inverted "); singleLinkedList.reverse(); singleLinkedList.list(); System. The out. Println (" chain length of the table: "+ singleLinkedList. GetLength ()); HeroNode lastIndexNode = singleLinkedList.findLastIndexNode(2); System.out.println(" lastIndexNode = "+lastIndexNode); singleLinkedList.list(); System.out.println(); singleLinkedList.reversePrint(); }}Copy the code

1.3. Two-way linked list

Two-way linked list is similar to one-way linked list, except

  • There is one more node in the structure of bidirectional linked list than unidirectional linked listpreDomain,prePoints to the node preceding the current node.
  • The direction of the one-way list can only be found (from front to back), while the two-way list can be forward and backward.
  • Unidirectional lists cannot self-delete (requiring secondary nodes), while bidirectional lists can self-delete

The following figure shows the structure of the two-way linked list:

The following uses a two-way linked list with head to achieve – water Margin hero leaderboard management to complete the hero of the add, delete and change traversal operation.

Add, delete, change and check thinking analysis

Creating a head node

class HeroNode2{ public int no; public String name; public String nickname; public HeroNode2 next; Public HeroNode2 pre; Public HeroNode2(int no, String name, String nickname) {this.no = no; this.name = name; this.nickname = nickname; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + ''' + ", nickname='" + nickname + ''' + '}'; }}Copy the code

Traverse the nodes

Bidirectional list traversal As with unidirectional lists, different bidirectional lists can be traversed backwards and forwards.

Add a node

There are two ways to add a node: to the end of the list and to the middle of the list

  • Add to tail: after the last node is traversed with secondary nodes

    
temp.next = newnode;
newnode.pre = temp; 
Copy the code

  • Add to the middle: After you find the right place, do the following


temp.next.pre=newnode
newnode.next=temp.next
newnode.pre=temp
temp.next=newnode
Copy the code

Remove nodes

After the node to be deleted is found, perform the following operations


temp.pre.next = temp.next;
temp.next.pre = temp.pre;
Copy the code

Modify the list

Modifying a linked list is the same as modifying a singly linked list.

The specific implementation

Class DoubleLinkedList{private HeroNode2 head = new HeroNode2(0,",""); Public HeroNode2 getHead() {return head; } /** * Add node * @param heroNode */ public void add(HeroNode2 heroNode){// define a secondary HeroNode2 temp = head; while (true){ if(temp.next == null){ break; } temp = temp.next; } temp.next = heroNode; heroNode.pre = temp; Public void addByOrder(HeroNode2 heroNode){// Define a secondary HeroNode2 temp = head; // define a secondary HeroNode2 temp = head; boolean falg = false; While (true){if(temp.next == null){break; } if(temp.next.no>heroNode.no){ break; }else if(temp.next.no == heroNode.no){ falg = true; break; } temp = temp.next; } if(! Falg){// not added to the end of the list if(temp.next! =null){ temp.next.pre = heroNode; heroNode.next = temp.next; } temp.next = heroNode; heroNode.pre = temp; }else{system.out.println (" cannot add, current information already exists "); }} @param heroNode2 */ public void update(heroNode2 heroNode2){if(head. System.out.println(" list is empty "); return; } // Define a secondary node HeroNode2 temp = head.next; boolean falg = false; While (true){if (temp. Next == null){return; If (temp.next. No == heronode2.no){falg = true; break; } temp = temp.next; } if(falg){ temp.next.name = heroNode2.name; temp.next.nickname = heroNode2.nickname; }else{system.out.println (" no data found ~~~"); }} /** * delete node * @param no */ public void del(int no){if(head.next == null){system.out.println (" list is empty ~~~~"); return; } HeroNode2 temp = head.next; boolean falg = false; while (true) { if(temp == null){ break; } if(temp.no == no){ falg = true; break; } temp = temp.next; } if(falg){ temp.pre.next = temp.next; if(temp.next! =null){ temp.next.pre = temp.pre; }}else{system.out.println (" the node to be deleted does not exist "); Public void list(){// define a secondary node HeroNode2 temp = head.next; If (temp == null){system.out.println (" list is empty ~~"); return; } while (true){ if(temp == null){ break; } System.out.println(temp); temp = temp.next; }}}Copy the code

1.4. The difference between arrays and linked lists

The list An array of
Memory footprint You don’t need continuous space You need continuous space
The size of the variable The size of a linked list can change dynamically The array size is fixed and cannot be dynamically expanded
Add or delete Fast, you only need to change the pointer to the previous element It’s slower. There’s a lot of elements to move
The query Slow, you can only traverse the query Fast, direct access by subscript
access The access must be sequential, not random Random access