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

This article introduces the relevant knowledge of "what are the knowledge points about the linked list". In the operation of actual cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

An one-way linked list

1.1 one-way linked list schematic

One link point of an one-way linked list contains a pointer to the data field and the next link node. The header node also contains data field and pointer domain, but generally, in order to facilitate search, the header node does not write data, and the pointer of the last node points to null.

1.2 realize the storage of one-way linked list and other operations

Create an entity class for a link node

Public class Node {/ / data field public long data; / / pointer domain public Node next; public Node (long value) {this.data = value;}}

1.2.1 insert a node

To insert a node after the header node, the first step is to point the newly inserted node to the node that the header node points to, and the second step is to point the header node to the newly inserted node. Inserting a node only needs to change one reference, so the complexity is O (1).

Public class LinkList {private Node head; / * insert a node after the header node * / public void insertFirst (long value) {Node node = new Node (value); node.next = head; head = node;}}

1.2.2 delete a node after the header node

To delete a node after the header node is to point the header node to the next node of the node. The complexity is also O (1).

Public Node deleteFirst () {Node tmp = head; head = tmp.next; return tmp;}

1.2.3 find nodes based on data domain

Searching needs to compare the data of each node. In theory, it takes two times to find a node on average, so the complexity is O (N).

Public Node find (long value) {Node current = head; while (current.data! = value) {if (current.next = = null) {return null;} current = current.next;} return current;}

1.2.4 deleting nodes based on data and

Searching needs to compare the data of each node. In theory, deleting a node takes two times on average, so the complexity is O (N).

Public Node delete (int value) {Node current = head; / / the previous node of the current node Node pre = head; while (current.data! = value) {if (current.next = = null) {return null;} pre = current; current = current.next;} if (current = = head) {head = head.next } else {pre.next = current.next;} return current;}

Double-ended linked list

2.1 double-ended linked list schematic

The double-ended linked list is based on the one-way linked list, and the head node adds a reference to the tail node.

2.2 realize the storage of double-ended linked list and other operations

2.2.1 insert a node from the head

If the linked list is empty, the setting tail node is the newly added node. The complexity is O (1).

Public class FirstLastLinkList {private Node first; private Node last; / * insert a node after the header node * / public void insertFirst (long value) {Node node = new Node (value); if (first = = null) {last = node;} node.next = first; first = node;}}

2.2.2 insert a node from the tail

If the linked list is empty, the header node is set to the newly added node, otherwise the last node of the tail node is set to the newly added node. The complexity is O (1).

Public void insertLast (long value) {Node node = new Node (value); if (first = = null) {first = node;} else {last.next = node;} last = node;}

2.2.3 remove from the header

Determine whether the head node has the next node, and if not, set the tail node to null with a complexity of O (1).

Public Node deleteFirst () {Node tmp = first; if (first.next = = null) {last = null;} first = tmp.next; return tmp;}

Three-way linked list

3.1 two-way linked list schematic diagram

Each node stores not only a reference to the latter node, but also a reference to the previous node.

3.2 implement the storage of two-way linked lists and other operations such as link node entity classes

Public class Node {/ / data field public long data; / / the latter node pointer domain public Node next; / / the previous node pointer domain public Node prev; public Node (long value) {this.data = value;}}

3.2.1 insert a node from the head

If the linked list is empty, the tail node is set to the newly added node, and if not empty, the previous node of the header node needs to be set as the newly added node. Inserting nodes only needs to change the references of two nodes, so the complexity is O (1).

Public class DoubleLinkList {private Node first; private Node last; / * insert a node after the header node * / public void insertFirst (long value) {Node node = new Node (value); if (first = = null) {last = node;} else {first.prev = node;} node.next = first First = node;}}

3.2.2 insert a node from the tail

If the linked list is empty, the header node is set to the newly added node, otherwise the last node of the tail node is set to the newly added node. At the same time, the previous node of the newly added node is set as the tail node. Inserting a node only needs to change the reference of one node, so the complexity is O (1).

Public void insertLast (long value) {Node node = new Node (value); if (first = = null) {first = node;} else {last.next = node; node.prev = last;} last = node;}

3.2.3 remove a node from the head

Determine whether the header node has the next node, if not, set the tail node to null, otherwise set the prev of the next node of the header node to null. The complexity is also O (1).

Public Node deleteFirst () {Node tmp = first; if (first.next = = null) {last = null;} else {first.next.prev = null;} first = tmp.next; return tmp;}

3.2.4 remove a node from the tail

If there are no other nodes after the head node, the head node is set to null, otherwise the next of the previous node of the tail node is set to null, and the tail node is set to the previous node. The complexity is O (1).

Public Node deleteLast () {Node tmp = last; if (first.next = = null) {first = null;} else {last.prev.next = null;} last = last.prev; return last;} "what are the knowledge points about linked lists"? thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.