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

This article mainly introduces the Java data structure and algorithm linked list example analysis, the article introduces in great detail, has a certain reference value, interested friends must read it!

1. A linked list (Linked List) A linked list usually consists of a series of nodes, each containing arbitrary instance data (data fields) and one or two links to the location of the previous / next node ("links")

A linked list (Linked list) is a common basic data structure, which is a linear table, but does not store data in a linear order, but a pointer (Pointer) to the next node in each node.

Using the linked list structure can overcome the disadvantage that the array linked list needs to know the data size in advance, and the linked list structure can make full use of the computer memory space to realize flexible memory dynamic management. However, the linked list loses the advantage of random reading of the array, and the linked list has a large space overhead due to the increase of the pointer domain of the node.

2. Unidirectional linked list (Single-Linked List)

The single linked list is the simplest in the linked list. The node of a single linked list (Node) is divided into two parts, the first part (data) stores or displays information about the node, and the other part stores the address of the next node. The portion of the last node's storage address points to a null value.

An one-way linked list can only be traversed in one direction. Generally, when looking for a node, you need to start from the first node and visit the next node at a time until the desired location. For inserting a node, for an one-way linked list, we only need to insert in the chain header, only need to set the current inserted node as the header node, and next points to the original header node. Delete a node, and we point the next of the previous node of that node to the next node of that node.

Add nodes to the header:

Delete a node:

①, specific implementation of one-way linked list package com.ys.datastructure;public class SingleLinkedList {number of private int size;// linked list nodes private Node head;// header node public SingleLinkedList () {size = 0; head = null;} / / each node class private class Node {private Object data;// data private Node next of each node of the linked list / / the connection of each node to the next node public Node (Object data) {this.data = data;}} / / add the element public Object addHead (Object obj) {Node newHead = new Node (obj) in the chain header; if (size = = 0) {head = newHead;} else {newHead.next = head; head = newHead } size++; return obj;} / / Delete the element public Object deleteHead () {Object obj = head.data; head = head.next; size--; return obj;} / / in the chain header, find the specified element, find the return node Node, and cannot find the return null public Node find (Object obj) {Node current = head Int tempSize = size; while (tempSize > 0) {if (obj.equals (current.data)) {return current;} else {current = current.next;} tempSize--;} return null } / / Delete the specified element. Successful deletion returns true public boolean delete (Object value) {if (size = = 0) {return false;} Node current = head; Node previous = head; while (current.data! = value) {if (current.next = = null) {return false } else {previous = current; current = current.next;}} / / if the deleted node is the first node if (current = = head) {head = current.next; size-- } else {/ / deleted node is not the first node previous.next = current.next; size--;} return true;} / / determine whether the linked list is empty public boolean isEmpty () {return (size = = 0) } / / display node information public void display () {if (size > 0) {Node node = head; int tempSize = size; if (tempSize = = 1) {/ / there is only one node System.out.println ("[" + node.data+ "]") in the current linked list; return } while (tempSize > 0) {if (node.equals (head)) {System.out.print ("[" + node.data+ "- >");} else if (node.next = = null) {System.out.print (node.data+ "]") } else {System.out.print (node.data+ "- >");} node = node.next; tempSize--;} System.out.println () } else {/ / if there are no nodes in the linked list, print [] System.out.println ("[]") directly;}

Test:

@ Testpublic void testSingleLinkedList () {SingleLinkedList singleList = new SingleLinkedList (); singleList.addHead ("A"); singleList.addHead ("B"); singleList.addHead ("C"); singleList.addHead ("D"); / / print current linked list information singleList.display (); / / Delete C singleList.delete ("C"); singleList.display (); / / find B System.out.println (singleList.find ("B"));}

Print the results:

②, using unidirectional linked list to realize stack

The pop () and push () methods of the stack correspond to deleting the element deleteHead () in the header of the linked list and adding the element addHead () in the header.

Package com.ys.datastructure;public class StackSingleLink {private SingleLinkedList link; public StackSingleLink () {link = new SingleLinkedList ();} / add element public void push (Object obj) {link.addHead (obj);} / / remove the top element public Object pop () {Object obj = link.deleteHead (); return obj } / / determine whether public boolean isEmpty () {return link.isEmpty ();} / print element information in the stack public void display () {link.display ();}} 4, double-ended linked list

For a single linked list, if we want to add a node to the tail, we must traverse from the head to the tail, find the tail node, and then insert a node after the tail node. This is troublesome, and it would be much easier if we had multiple references to the tail node when designing the linked list.

Pay attention to the difference between the two-way linked list and the following!

Specific implementation of ① and double-ended linked list package com.ys.link;public class DoublePointLinkedList {private Node head;// header node private Node tail;// tail node number of private int size;// nodes private class Node {private Object data; private Node next; public Node (Object data) {this.data = data;}} public DoublePointLinkedList () {size = 0 Head = null; tail = null;} / / the new node in the chain header public void addHead (Object data) {Node node = new Node (data); if (size = = 0) {/ / if the list is empty, then both the header node and the tail node are the new node head = node; tail = node; size++ } else {node.next = head; head = node; size++;}} / / add a new node at the end of the list public void addTail (Object data) {Node node = new Node (data); if (size = = 0) {/ / if the list is empty, then both the header node and the tail node are the new node head = node Tail = node; size++;} else {tail.next = node; tail = node; size++;}} / / Delete the header node, true is returned successfully, and false public boolean deleteHead () {if (size = = 0) {/ / the number of nodes in the current chain is 0 return false for failure } if (head.next = = null) {/ / the number of nodes in the current chain is 1 head = null; tail = null;} else {head = head.next;} size--; return true;} / / determine whether it is empty public boolean isEmpty () {return (size = = 0) } / / get the number of nodes in the linked list public int getSize () {return size;} / / display node information public void display () {if (size > 0) {Node node = head; int tempSize = size If (tempSize = = 1) {/ / the current linked list has only one node System.out.println ("[" + node.data+ "]"); return;} while (tempSize > 0) {if (node.equals (head)) {System.out.print ("[" + node.data+ "- >") } else if (node.next = = null) {System.out.print (node.data+ "]");} else {System.out.print (node.data+ "- >");} node = node.next; tempSize-- } System.out.println ();} else {/ / if there are no nodes in the linked list, print [] System.out.println ("[]") directly;}} ②, and use double-ended linked list to implement queue package com.ys.link;public class QueueLinkedList {private DoublePointLinkedList dp; public QueueLinkedList () {dp = new DoublePointLinkedList () } public void insert (Object data) {dp.addTail (data);} public void delete () {dp.deleteHead ();} public boolean isEmpty () {return dp.isEmpty ();} public int getSize () {return dp.getSize ();} public void display () {dp.display ();}} 5, Abstract data Type (ADT)

When introducing abstract data types, let's first look at what data types are. When we hear this word, we may first think of words like int,double in Java, which is the basic data type in Java. A data type involves two things:

①, data items with specific characteristics

②, operations allowed on data

For example, the int data type in Java represents an integer with values ranging from-2147483648 to 2147483647. It can also be operated with various operators, such as +, -, *, /, and so on. The operations allowed by the data type are an inseparable part of itself, and understanding the type includes understanding what operations can be applied to the type.

So why did the people who designed computer languages consider data types?

Let's first look at such an example, for example, everyone needs to live in a house, and they all want the bigger the better. But obviously, without money, there is no point in thinking about a house. As a result, there are all kinds of commercial housing, including villas, duplex, staggered floors, single rooms. There is even a capsule room of only two square meters. The meaning of this is to meet the needs of different people.

Similarly, the same problem exists in computers. Calculating expressions like 1 to 1 does not require a lot of storage space, nor does it require memory space suitable for decimal or even character operations. So computer researchers consider the need to classify the data into a variety of data types. Such as int, such as float.

Although different computers have different hardware systems, in fact, high-level language writers do not care what computer the program is running on, and their purpose is to realize the operation of shaping numbers, such as afigb, and so on. They don't care how integers are represented inside the computer, or how CPU is calculated. So we consider that no matter what computer or language will face a similar integer operation, we can consider abstracting it. Abstraction is to extract the universal nature of things, is a summary of things, is a way of thinking.

Abstract data type (ADT) refers to a mathematical model and a set of operations defined on the model. It only depends on its logical characteristics, and has nothing to do with how it is represented and implemented in the computer. For example, every computer, no matter mainframe, minicomputer, PC, tablet computer or even smartphone, has "integer" type and needs plastic operation, so integer is actually an abstract data type.

More broadly, for example, the stack and queue data structures we just described, we use arrays and linked lists respectively, such as stacks. For users who only need to know the existence of pop () and push () methods or other methods and how to use them, users do not need to know the array or linked list we are using.

The idea of ADT can be used as the idea of our design tool, for example, if we need to store data, do we need to access the last data item by considering the operations that need to be implemented on the data? Or the first one? Or an item with a specific value? Or is it an item in a specific location? Answering these questions leads to the definition of ADT, and only after a complete definition of ADT should you consider the details of the implementation.

This interface design concept in our Java language makes sense.

6. Ordered linked list

The previous linked list implementation of inserting data is unordered, and in some applications, the data in the linked list needs to be ordered, which is called ordered linked list.

In an ordered linked list, the data is arranged in order according to key values. In general, ordered linked lists can also be used in most cases where ordered arrays are needed. Where ordered linked lists are superior to ordered arrays is the speed of insertion (because elements do not need to be moved), and linked lists can be extended to all effective memory use, while arrays can only be limited to a fixed size.

Package com.ys.datastructure;public class OrderLinkedList {private Node head; private class Node {private int data; private Node next; public Node (int data) {this.data = data;}} public OrderLinkedList () {head = null;} / / insert nodes and arrange public void insert (int value) {Node node = new Node (value) in the order from small to Node pre = null; Node current = head; while (current! = null & & value > current.data) {pre = current; current = current.next;} if (pre = = null) {head = node; head.next = current;} else {pre.next = node; node.next = current }} / / Delete header public void deleteHead () {head = head.next;} public void display () {Node current = head; while (current! = null) {System.out.print (current.data+ ""); current = current.next;} System.out.println ("");}}

Inserting and deleting an item in an ordered list requires a maximum of O (N) comparisons, with an average of O (N), because you have to follow the linked list step by step to find the correct insertion position, but you can delete the maximum value as quickly as possible, because you only need to delete the header, if an application needs frequent access to the minimum value and does not need to insert quickly. Then the ordered linked list is a better choice. For example, priority queues can be implemented using ordered linked lists.

7. Sort by combining ordered linked list and unordered array

For example, if there is an unordered array that needs to be sorted, we need O (N2) when we explain three simple sorts of sorting: bubble sort, selection sort, and insert sort.

Now that we have explained the ordered linked list, for an unordered array, we first take out the array elements, insert them one by one into the ordered linked list, and then delete them from the ordered linked list and put them back into the array. Then the array will be sorted. As with the insertion sort, if N new data are inserted, then about N2jump 4 comparisons are made. But compared to insert sort, each element is sorted only twice, once from array to linked list and once from linked list to array, which takes about 2N moves, while insert sort requires N2 moves.

It is certainly more efficient than the simple sorting mentioned earlier, but the disadvantage is that it needs to open up almost twice as much space, and the array and linked list must exist in memory at the same time, so this method is good if there is a ready-made linked list available.

8. Two-way linked list

We know that an one-way linked list can only be traversed in one direction, so a two-way linked list can traverse in both directions.

Specific code implementation:

Package com.ys.datastructure;public class TwoWayLinkedList {private Node head;// for chain header private Node tail;// for chain footer private int size;// for number of nodes in linked list private class Node {private Object data; private Node next; private Node prev; public Node (Object data) {this.data = data;}} public TwoWayLinkedList () {size = 0 Head = null; tail = null;} / / add node public void addHead (Object value) {Node newNode = newNode (value) to the chain header; if (size = = 0) {head = newNode; tail = newNode; size++;} else {head.prev = newNode; newNode.next = head Head = newNode; size++;}} / / add node public void addTail (Object value) {Node newNode = newNode (value) to the end of the chain list; if (size = = 0) {head = newNode; tail = newNode; size++;} else {newNode.prev = tail; tail.next = newNode Tail = newNode; size++;}} / / Delete chain header public Node deleteHead () {Node temp = head; if (size! = 0) {head = head.next; head.prev = null; size--;} return temp } / / Delete the tail of the linked list public Node deleteTail () {Node temp = tail; if (size! = 0) {tail = tail.prev; tail.next = null; size--;} return temp;} / / get the number of nodes in the linked list public int getSize () {return size } / / determine whether the linked list is empty public boolean isEmpty () {return (size = = 0);} / / display node information public void display () {if (size > 0) {Node node = head; int tempSize = size If (tempSize = = 1) {/ / the current linked list has only one node System.out.println ("[" + node.data+ "]"); return;} while (tempSize > 0) {if (node.equals (head)) {System.out.print ("[" + node.data+ "- >") } else if (node.next = = null) {System.out.print (node.data+ "]");} else {System.out.print (node.data+ "- >");} node = node.next; tempSize-- } System.out.println ();} else {/ / if there are no nodes in the linked list, print [] System.out.println ("[]") directly;}

We can also use two-way linked lists to implement double-ended queues, so there is no specific code demonstration here.

The above is all the contents of the article "sample Analysis of linked lists of Java data structures and algorithms". Thank you for reading! Hope to share the content to help you, more related 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.