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

Editor to share with you what is an one-way linked list and two-way linked list in java, I believe most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

1. Introduction to linked list 1. Concept of linked list

The linked list is a non-continuous and non-sequential storage structure on the physical storage unit, and the logical order of data elements is realized by the pointer link order in the linked list. The linked list consists of a series of nodes, which can be generated dynamically at run time. The node consists of two parts: one is the data field where the data elements are stored, and the other is the pointer domain that stores the address of the next node.

2. Basic characteristics

Memory storage

Logical structure

Characteristic description

Physical storage is disordered and discontiguous

A linked list is made up of multiple nodes with a linked structure.

Logically, an orderly link structure is formed.

Linked list structure solves the defect that array storage needs to know the number of elements in advance, and can make full use of memory space to achieve flexible memory dynamic management.

One-way linked list 1. Basic description

One-way linked list is a kind of linked list, which is characterized by that the link direction of the linked list is unidirectional, and the traversal of the linked list should be read sequentially from the head; node composition, the head pointer points to the first to become the header node, terminating at the last pointer to NULL.

2. Basic operation

Add data

Initialize the head node as the header of the linked list

Modify the next pointer of the current end node

The newly added node house is at the end of the linked list

Delete data

Traverse to find the node to be deleted, and point the pointer of the previous node to the next node of the deleted node.

III. Two-way linked list 1. Concept description

Two-way linked list, also known as double-linked list, is a kind of linked list. There are two pointers in each data node of the linked list, pointing to the direct successor and the direct precursor, respectively. Starting from any node in the two-way linked list, its precursor node and successor node can be accessed very quickly. Most of the linked list structure is to construct a two-way circular linked list.

2. Basic operation

Add data

Traverse to find the last node of the linked list

Modify the next pointer of the current end node

The newly added node house is at the end of the linked list

Add the prev pointer to the latest tail node

Delete data

Two-way linked list, based on the operation to delete the node

Operate the Node2 node to be deleted in the figure above

Node2.prev.next = Node2.next

Node2.next.prev = Node2.prev

Through the operation of the above process, one node in the linked list is deleted, and the remaining nodes are connected into a chain structure again.

3. Source code analysis

In Java's API, LinkedList is a typical two-way linked list structure, the following is based on the LinkedList source code to see the two-way linked list operation.

Basic case

Public class M01_Linked {public static void main (String [] args) {List userList = new LinkedList (); User removeUser = new User (200, "Second"); / / add elements userList.add (new User (100, "First"); userList.add (removeUser); userList.add (new User (300, "Third")) System.out.println ("initialization:" + userList); / / modify element userList.get (0). SetUserName ("Zero"); System.out.println ("modified:" + userList "); / / delete element userList.remove (removeUser); System.out.println (" after deletion: "+ userList);}} class User {private Integer userId; private String userName Public User (Integer userId, String userName) {this.userId = userId; this.userName = userName;} @ Override public String toString () {return "User {" + "userId=" + userId + ", userName='" + userName +'\'+'}';} / / omit Get and Set methods}

Node description

There are three core descriptions of nodes: data, next pointer and prev pointer.

Private static class Node {E item; / / data Node next; / / next pointer Node prev; / / previous pointer Node (Node prev, E element, Node next) {this.item = element; this.next = next; this.prev = prev;}}

First node processing

Based on the LinkedList source code, head and tail node mode, in view of the above figure double linked list of the first pointer characteristics, here the source code is easy to understand.

Public class LinkedList {transient Node first; transient Node last; / / processing head node private void linkFirst (E e) {final Node f = first; final Node newNode = newNode (null, e, f); first = newNode; if (f = = null) last = newNode; else f.prev = newNode } / / processing tail node void linkLast (E e) {final Node l = last; final Node newNode = newNode (l, e, null); last = newNode; if (l = = null) first = newNode; else l.next = newNode;}

Add nod

The method of adding a node directly calls the linkLast method and puts the new node at the end of the linked list.

Public boolean add (E e) {linkLast (e); return true;}

Delete nod

Step 1: traverse the comparison to find the node you want to delete

Public boolean remove (Object o) {if (o = = null) {for (Node x = first; x! = null; x = x.next) {if (x.item = = null) {unlink (x); return true;}} else {for (Node x = first; x! = null) X = x.next) {if (o.equals (x.item)) {unlink (x); return true;} return false;}

Step 2: remove the node, rebuild the linked list structure, set the data of the current linked list to null, and return the removed node

E unlink (Node x) {final E element = x.item; final Node next = x.next; final Node prev = x.item; if (prev = = null) {first = next;} else {prev.next = next; x.prev = null;} if (next = = null) {last = prev;} else {next.prev = prev; x.next = null } x.item = null; return element;}

As above is part of the structural analysis of the source code of the LinkedList double-chain table in Java, this kind of code has seen too much, always feel that the code they write is not Java.

Circular linked list

In a single linked list, change the pointer field NULL of the terminal node to point to the header node or start node, thus forming a circular linked list:

A structure of a linked list characterized by the fact that the pointer domain of the last node in the table points to the head node, and the whole linked list forms a ring.

The above is all the contents of the article "what is an one-way linked list and a two-way linked list in java". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

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.