Shulou(Shulou.com)06/03 Report--

This article shares with you the contents of the two-way linked list, circular linked list and example analysis of the Joseph problem of Java data structures and algorithms. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

I. two-way linked list

Using two-way linked list with head head-Analysis of the shortcomings of one-way linked list managed by Shuihu Heroes list:

One-way linked list, the search direction can only be in one direction, while two-way linked list can be looked forward or backward.

The one-way linked list cannot delete itself, it needs to rely on the auxiliary node, while the two-way linked list can delete itself, so when we delete a node in a single linked list, we always find the previous node of the node to be deleted when the temp,temp is to be deleted.

Analyze the operation ideas of traversing, adding, modifying and deleting two-way linked list.

1. Traversal is the same as a single linked list, except that you can look forward or backward.

two。 Add (add to the end of the two-way linked list by default)

First find the last node of the two-way linked list

Temp.next = newHeroNode

NewHeroNode.pre = temp

3. The idea and principle of modification is the same as an one-way linked list.

4. Delete

Because of the two-way linked list, we can delete a node by ourselves.

Go directly to the node to be deleted, such as temp

Temp.pre.next = temp.next

Temp.next.pre = temp.pre

Public class DoubleLinkedListDemo {public static void main (String [] args) {/ / Test System.out.println ("Test of two-way linked lists"); / / create nodes HeroNode2 hero1 = new HeroNode2 (1, "Song Jiang", "timely Rain") HeroNode2 hero2 = new HeroNode2 (2, "Lu Junyi", "Jade Kirin"); HeroNode2 hero3 = new HeroNode2 (3, "Wu Yong", "Zhi Duoxing"); HeroNode2 hero4 = new HeroNode2 (4, "Lin Chong", "Leopard head"); / / create a two-way linked list DoubleLinkedList doubleLinkedList = new DoubleLinkedList () / / add doubleLinkedList.add (hero1); doubleLinkedList.add (hero2); doubleLinkedList.add (hero3); doubleLinkedList.add (hero4); doubleLinkedList.list (); / / modify HeroNode2 newHeroNode = new HeroNode2 (4, "Gongsun Sheng", "Jinyunlong") DoubleLinkedList.update (newHeroNode); System.out.println ("modified linked list"); doubleLinkedList.list (); / / delete doubleLinkedList.del (3); System.out.println ("deleted linked list ~"); doubleLinkedList.list () }} / / create a two-way linked list class class DoubleLinkedList {/ / initialize a header node first, do not move the header node, and do not store specific data private HeroNode2 head = new HeroNode2 (0, ","); / / return public HeroNode2 getHead () {return head } / / display linked list [traversal] public void list () {/ / determine whether the linked list is empty if (head.next = = null) {System.out.println ("linked list is empty"); return } / / because the header node cannot be moved, we need an auxiliary variable to iterate through HeroNode2 temp = head.next While (true) {/ / determine whether to reach the last if of the linked list (temp = = null) {break;} / / output node information System.out.println (temp) / / move temp back, be careful temp = temp.next }} / / add a node to the last public void add (HeroNode2 heroNode) of the two-way linked list {/ / because the head node cannot be moved, we need an auxiliary variable temp HeroNode2 temp = head / / iterate through the linked list, find the last while (true) {/ / find the last if of the linked list (temp.next = = null) {break } / / if the final is not found, move temp back to temp = temp.next;} / / when exiting the while loop, temp points to the last / / of the linked list to form a two-way linked list temp.next = heroNode HeroNode.pre = temp } / / modify the content of a node, the node content of the two-way linked list is the same as the one-way linked list / / except that the node type is changed to HeroNode2 public void update (HeroNode2 newHeroNode) {/ / to determine whether if (head.next = = null) {System.out.println ("the linked list is empty ~") Return;} / / find the node that needs to be modified, and define an auxiliary variable HeroNode2 temp = head.next; boolean flag = false according to the no number / / / / indicates whether the node while (true) {if (temp = = null) {break is found / / has finished traversing the linked list} if (temp.no = = newHeroNode.no) {/ / found flag = true; break } temp = temp.next;} / / judge whether to find the node to be modified according to flag if (flag) {temp.name = newHeroNode.name; temp.nickname = newHeroNode.nickname } else {/ / No System.out.printf was found ("No node numbered% d was found, cannot be modified\ n", newHeroNode.no);}} / / remove a node from the two-way linked list / / description / / 1. For the two-way linked list, we can directly find the node / / 2 to be deleted. After finding it, public void del (int no) {/ / determine whether the current linked list is empty if (head.next = = null) {/ / empty linked list System.out.println ("the linked list is empty and cannot be deleted"); return } HeroNode2 temp = head.next;// auxiliary variable (pointer), pointing to the first node (different from the one-way linked list) boolean flag = false / / Mark whether to find the next break of the node to be deleted while (true) {if (temp.next = = null) {/ / to the last node of the linked list } if (temp.next.no = = no) {/ / the previous node of the node to be deleted found temp flag = true; break } temp = temp.next;// temp moves backward, traversing} / / determines that flag if (flag) {/ / find / / can delete temp.pre.next = temp.next / / if it is the last node, you do not need to execute the following sentence, otherwise a null pointer if (temp.next! = null) {temp.next.pre = temp.pre will appear. }} else {System.out.printf ("% d node to be deleted does not exist\ n", no);} / / define HeroNode2, each HeroNode object is a node class HeroNode2 {public int no; public String name; public String nickname; public HeroNode2 next / / points to the next node. Default is null public HeroNode2 pre;// points to the previous node, and default is null / / constructor public HeroNode2 (int no, String name, String nickname) {this.no = no; this.name = name; this.nickname = nickname } / / for display convenience, we rewrite toString @ Override public String toString () {return "HeroNode2 [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";}} II. Circular linked list and its applications: Joseph problem

Circular linked list diagram

The idea of constructing an one-way circular linked list

1. First create the first node, let first point to it, and form a ring

two。 Later, every time we create a new node, we can add it to the existing circular linked list.

Traversing circular linked list

1. First let an auxiliary pointer (variable) curBoy, which points to the first node

two。 Then cur.Boy.next = = first ends by traversing the circular linked list through a while loop

Joseph problem

1. Create an auxiliary pointer (variable) helper that should point to the last node of the circular linked list in advance.

two。 Before the child counts, let first and helper move k-1 times (to the child who counts)

3. When the child counts, let the first and helper pointer move m-1 times at the same time

4. At this point, the child node pointed by first can be out of the circle.

First = first.next

Helper.next = first

The node pointed to by the original first does not have any references and will be recycled

Public class Josepfu {public static void main (String [] args) {/ / Test to see if building a circular linked list and traversing whether ok CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList (); circleSingleLinkedList.addBoy (5); / / add 5 child nodes circleSingleLinkedList.showBoy () / / Test whether the child is out of the circle correctly circleSingleLinkedList.countBoy (1, 2, 5); / / 2-> 4-> 1-> 5-> 3}} / / create a circular one-way linked list class CircleSingleLinkedList {/ / create a first node, currently there is no number private Boy first = null / / add a child node to build a circular linked list public void addBoy (int nums) {/ / nums to do a data check if (nums < 1) {System.out.println ("incorrect value of nums"); return } Boy curBoy = null;// auxiliary pointer to help build a circular linked list / / use for to create a circular linked list for (int I = 1; I nums) {System.out.println ("parameter input error, please re-enter"); return } / / create an auxiliary pointer to help the child get out of the circle Boy helper = first / / you need to create an auxiliary pointer (variable) helper, which should point to the last node of the circular linked list, while (true) {if (helper.getNext () = = first) {/ / indicate that helper points to the last child node break. } helper = helper.getNext ();} / / Let first and helper move for k-1 (int j = 0; j < startNo-1; jacks +) {first = first.getNext () before the child counts. Helper = helper.getNext () } / / when the child counts, let the first and helper pointer move m-1 at the same time, and then circle / / here is a circular operation Until there is only one node in the circle while (true) {if (helper = = first) {/ / indicates that there is only one node break in the circle } / / Let the first and helper pointers move countNum-1 for at the same time (int j = 0; j < countNum-1; jacks +) {first = first.getNext (); helper = helper.getNext () } / / the node first points to is the child node System.out.printf ("child% d out of circle\ n", first.getNo ()); / / the child node pointed to by first is out of circle first = first.getNext () Helper.setNext (first);} System.out.printf ("last child number% d\ n", first.getNo ());}} / / create a Boy class that represents a node class Boy {private int no;// number private Boy next / / points to the next node. Default null public Boy (int no) {this.no = no;} public int getNo () {return no;} public void setNo (int no) {this.no = no;} public Boy getNext () {return next } public void setNext (Boy next) {this.next = next;}} Thank you for reading! On the "Java data structure and algorithm of the two-way linked list, circular linked list and Joseph problem example analysis" this article is shared here, I hope the above content can be of some help to you, so that you can learn more knowledge, if you think the article is good, you can share it out for more people to see it!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.