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

This article mainly introduces Java how to achieve headless two-way linked list operation, has a certain reference value, interested friends can refer to, I hope you can learn a lot after reading this article, the following let the editor take you to understand it.

The details are as follows

The structure of headless two-way linked list:

Code analysis

Node structure

Class Node {private int data; private Node next; private Node prev; public Node (int data) {this.data = data; this.prev = null; this.next = null;}} private Node head; / / header private Node last; / / tail public DoubleLinked () {this.head = null; this.last = null;}

1. Head insertion method

/ * 1. Head insertion * @ param data*/public void addFirst (int data) {Node node = new Node (data); if (this.head = = null) {this.head = node; this.last = node;} else {node.next = this.head; this.head.prev = node; this.head = node;}}

First determine whether the linked list is empty, if so, insert directly, and both the header node and the tail node point directly to the newly inserted element.

If the linked list is not empty, point the next of the node to be inserted to the chain header node, the prev of the header node to the newly inserted node, and finally update the header node to the newly inserted node. The insertion process is shown below:

two。 Tail insertion method

/ * * 2. Tail interpolation * @ param data*/public void addLast (int data) {Node node = new Node (data); if (this.head = = null) {this.head = node; this.last = node;} else {this.last.next = node; node.prev = this.last; this.last = node;}}

If the linked list is empty, insert with the same head

If the list is not empty, point the next of the tail node of the list to the node to be inserted, the prev of the node to be inserted points to the tail node of the list, and finally update the tail node to the new insertion node. The insertion process is shown below:

3. Find out whether the keyword key is included in the single linked list

/ / find private Node searchIndex (int index) {checkIndex (index); int count = 0; Node cur = this.head; while (count! = index) {cur = cur.next; count++;} return cur;} / / validity check private void checkIndex (int index) {if (index)

GetLength () {throw new IndexOutOfBoundsException ("subscript is invalid!") ;} / * * 3. Insert anywhere, the first data node is the 0 subscript * @ param index insertion position * @ param data inserted value * @ return true/false * / @ Override public boolean addIndex (int index, int data) {if (index = = 0) {addFirst (data); return true } if (index = = getLength ()) {addLast (data); return true;} / / cur points to the node at index location Node cur = searchIndex (index); Node node = new Node (data); node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node Return true;}

4. Find out whether the keyword key is included in the single linked list

/ * * 4. Find out whether the keyword key is included in the single linked list * @ param key keyword * @ return true/false * / @ Overridepublic boolean contains (int key) {Node cur = this.head; while (cur! = null) {if (cur.data = = key) {return true;} cur = cur.next;} return false;}

5. Delete the node whose keyword is key for the first time

/ * * 5. Delete the node whose keyword is key for the first time * @ param key * @ return * / @ Overridepublic int remove (int key) {Node cur = this.head; int oldData = 0; while (cur! = null) {if (cur.data = = key) {oldData = cur.data / / header node if (cur = = this.head) {this.head = this.head.next; this.head.prev = null } else {/ / cur.next! = null-> is not the tail node if (cur.next! = null) {cur.next.prev = cur.prev;} else {this.last = cur.prev;} return oldData } cur = cur.next;} return-1;}

6. Delete all nodes with a value of key

/ * 6. Delete all nodes with a value of key * @ param key * / @ Overridepublic void removeAllKey (int key) {Node cur = this.head; while (cur! = null) {if (cur.data = = key) {/ / header if (cur = = this.head) {this.head = this.head.next; this.head.prev = null } else {cur.prev.next = cur.next; / / cur.next! = null-> is not the tail node if (cur.next! = null) {cur.next.prev = cur.prev;} else {this.last = cur.prev } cur = cur.next;}}

7. Get the length of a single linked list

/ * 7. Get the length of the single linked list * @ return * / @ Overridepublic int getLength () {int count = 0; Node cur = this.head; while (cur! = null) {count++; cur = cur.next;} return count;}

8. Print linked list

/ * 8. Print linked list * / @ Overridepublic void display () {if (this.head = = null) {return;} Node cur = this.head; while (cur! = null) {System.out.print (cur.data + ""); cur = cur.next;} System.out.println ();}

9. Empty the sequence table to prevent memory leaks

/ * * 9. Clear the sequence table to prevent memory leaks * / @ Overridepublic void clear () {while (this.head! = null) {Node cur = this.head.next; this.head.next = null; this.head.prev = null; this.head = cur;}} interface, implementation method, test

1. Interface

Package com.github.doubly;// does not lead the implementation of node single linked list public interface IDoubleLinked {/ / 1. Head insertion void addFirst (int data); / / 2. Tail interpolation void addLast (int data); / / 3. Insert anywhere, the first data node is 0 subscript boolean addIndex (int index, int data); / / 4. Find whether to include the keyword key in the single linked list boolean contains (int key); / / 5. Delete the node int remove (int key) whose keyword is key for the first time; / / 6. Delete all nodes with the value of key void removeAllKey (int key); / / 7. Get the length of the single linked list int getLength (); / / 8. Print the linked list void display (); / / 9. Clear the sequence table to prevent memory leaks void clear ();}

two。 Realization method

Package com.github.doubly;public class DoubleLinked implements IDoubleLinked {class Node {private int data; private Node next; private Node prev; public Node (int data) {this.data = data; this.prev = null; this.next = null;}} private Node head; / / header private Node last / / tail node public DoubleLinked () {this.head = null; this.last = null;} / * 1. Head insertion * @ param data * / @ Override public void addFirst (int data) {Node node = new Node (data); if (this.head = = null) {this.head = node; this.last = node;} else {node.next = this.head; this.head.prev = node; this.head = node } / * 2. Tail interpolation * @ param data * / @ Override public void addLast (int data) {Node node = new Node (data); if (this.head = = null) {this.head = node; this.last = node;} else {this.last.next = node; node.prev = this.last; this.last = node }} / / find private Node searchIndex (int index) {checkIndex (index); int count = 0; Node cur = this.head; while (count! = index) {cur = cur.next; count++;} return cur;} / / validity check private void checkIndex (int index) {if (index)

GetLength () {throw new IndexOutOfBoundsException ("subscript is invalid!") ;} / * * 3. Insert anywhere, the first data node is the 0 subscript * @ param index insertion position * @ param data inserted value * @ return true/false * / @ Override public boolean addIndex (int index, int data) {if (index = = 0) {addFirst (data); return true } if (index = = getLength ()) {addLast (data); return true;} / / cur points to the node at index location Node cur = searchIndex (index); Node node = new Node (data); node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node Return true;} / * 4. Find whether to include the keyword key in the single linked list * @ param key to find the keyword * @ return true/false * / @ Override public boolean contains (int key) {Node cur = this.head; while (cur! = null) {if (cur.data = = key) {return true;} cur = cur.next } return false;} / * 5. Delete the node whose keyword is key for the first time * @ param key * @ return * / @ Override public int remove (int key) {Node cur = this.head; int oldData = 0; while (cur! = null) {if (cur.data = = key) {oldData = cur.data / / header node if (cur = = this.head) {this.head = this.head.next; this.head.prev = null } else {/ / cur.next! = null-> is not the tail node if (cur.next! = null) {cur.next.prev = cur.prev;} else {this.last = cur.prev }} return oldData;} cur = cur.next;} return-1;} / * * 6. Delete all nodes with a value of key * @ param key * / @ Override public void removeAllKey (int key) {Node cur = this.head; while (cur! = null) {if (cur.data = = key) {/ / header if (cur = = this.head) {this.head = this.head.next This.head.prev = null;} else {cur.prev.next = cur.next; / / cur.next! = null-> not the tail node if (cur.next! = null) {cur.next.prev = cur.prev } else {this.last = cur.prev;} cur = cur.next;}} / * * 7. Get the length of the single linked list * @ return * / @ Override public int getLength () {int count = 0; Node cur = this.head; while (cur! = null) {count++; cur = cur.next;} return count;} / * 8. Print linked list * / @ Override public void display () {if (this.head = = null) {return;} Node cur = this.head; while (cur! = null) {System.out.print (cur.data + ""); cur = cur.next;} System.out.println () } / * * 9. Empty the sequence table to prevent memory leaks * / @ Override public void clear () {while (this.head! = null) {Node cur = this.head.next; this.head.next = null; this.head.prev = null; this.head = cur;}

3. test

Package com.github.doubly;public class TestDemo {public static void main (String [] args) {DoubleLinked doubleLinked = new DoubleLinked (); doubleLinked.addFirst (10); doubleLinked.addFirst (20); doubleLinked.addFirst (30); doubleLinked.addFirst (40); doubleLinked.addFirst (50); doubleLinked.display (); doubleLinked.addIndex (0100); doubleLinked.addIndex (1200) DoubleLinked.addIndex (0300); doubleLinked.addLast (40); doubleLinked.addLast (50); doubleLinked.display (); doubleLinked.remove (300); doubleLinked.display (); doubleLinked.removeAllKey (50); doubleLinked.display ();}}

Thank you for reading this article carefully. I hope the article "how to achieve headless two-way linked list operation in Java" shared by the editor will be helpful to everyone. At the same time, I also hope that you will support and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

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.