I Linked list
When you need to dynamically reduce or increase data items, you can use the linked list data structure
Linked list is a data structure composed of several objects called nodes. Each node contains one data and the reference of the next node (single linked list), or one data and the reference of the previous node and the reference of the next node (double linked list)
Single chain indicates intention
Double chain indicates intention
LinkedList < E > generic class
java. The objects created by the LinkedList < E > generic class in util package store data in a linked list structure. Traditionally, the objects created by the LinkedList class are called linked list objects.
LinkedList<String>mylist = new LinkedList<String>();
Create an empty double linked list.
When using LinkedList < E > generic class to declare and create a linked list, you must specify the specific type of E, and then the linked list can use the add(E obj) method to add nodes to the linked list in turn.
The above linked list mylist uses the add method to add nodes. The data in the nodes must be String objects,
mylist.add("How");
mylist.add("Are");
mylist.add("You");
mylist.add("Java");The linked list mylist has four nodes. The nodes are automatically linked together and do not need to be linked. In other words, there is no need to operate and arrange the reference of the next or previous node stored in the node.
Listedlist < E > common methods of generic classes
LinkedList < E > is a generic class that implements the generic interface list < E >, and the generic interface list < E > is a sub interface of the collection < E > generic interface. Most methods in LinkedList < E > generic classes are the implementation of generic interface methods.
When programming, you can use interface callback technology, that is, assign the reference of LinkedList < E > object to collection < E > interface variable or list < E > interface variable, and then the interface can call the interface method implemented by the class.
The following is the LinkedList < E > generic class, which implements some common methods in the list < E > generic interface.
public boolean add(E element): add a new node to the end of the linked list. The data in this node is the data specified by the parameter element.
public void add(int index, E element): add a new node to the specified location of the linked list. The data in the node is the data specified by the parameter element.
public void clear(): delete all nodes of the linked list to make the current linked list empty.
public # E # remove(int # index): deletes a node at a specified location.
public boolean remove(E element): delete the node containing data element for the first time.
public # E # get(int # index): get the data in the node where the pointer is located in the linked list.
public # int # indexOf(E # element): returns the first occurrence position of the node containing data # element in the linked list. If there is no such node in the linked list, it returns - 1.
public # int # lastIndexOf(E # element): returns the last position of the node containing data # element in the linked list. If there is no such node in the linked list, it returns - 1.
public E set(int index,E element); Replace the data in the location node of the current linked list index with the data specified by the parameter element, and return the replaced data.
public int size(): returns the length of the linked list, that is, the number of nodes.
public # boolean # contains (Object # element): judge whether any node in the linked list contains data
element.
The following are the newly added common methods of LinkedList < E > generic class itself
public void addFirst(E element): add a new node to the head of the linked list. The data in this node is a parameter
element.
public # void # addLast(E # element): add a new node to the end of the linked list. The data in this node is the data specified by the parameter # elemt.
public # E # getFirst(): get the data in the first node in the linked list.
public # E # getLast(): get the data in the last node in the linked list.
public # removeFirst(): delete the first node and return the data in this node.
public # removeLast(): delete the last node and return the data in this node.
public Object clone(): get a cloned linked list of the current linked list. The change of node data in the cloned linked list will not affect the data of nodes in the current linked list.
Traversal linked list
No matter what kind of collection, the customer should be allowed to traverse the objects in the collection in some way without knowing how these objects are represented and stored in the collection. The Java collection framework provides a generation selector for the collection of various data structures, such as linked list, hash table and other different storage structures.
Some collections also provide methods to return data according to their data storage structure and operations. For example, the get(int index) method in the LinkedList class will return the object in the index node in the current linked list. The storage structure of LinkedList ， is not a sequential structure. Therefore, the speed of the linked list calling the get(int ， index) method is slower than that of the set of sequential storage structure calling the get(int ， index) method. Therefore, when users need to traverse the objects in the collection, they should use the generation selector provided by the collection, rather than let the collection itself traverse the objects in it. Because the method of traversing the set by the selector not only finds an object in the set, but also gets the reference of the successor object to be traversed, the selector can traverse the set quickly.
The linked list object can use the iterator() method to obtain an Iterator object, which is the Iterator for the current linked list.
The following comparison uses the time taken to traverse the linked list from iteration and get(int index) method:
import java.util.Iterator;
import java.util.LinkedList;
public class Ex13_3 {
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList<String> list = new LinkedList<String>();
for(int i=0;i<=60096;i++) {
list.add("speed"+i);
}
Iterator<String> iter = list.iterator();
long starttime = System.currentTimeMillis();
while(iter.hasNext()) {
String te = iter.next();
}
long endTime = System.currentTimeMillis();
long result = endTime-starttime;
System.out.println("Time spent traversing the collection using iterators:"+result+"millisecond");
starttime=System.currentTimeMillis();
for(int i=0;i<list.size();i++) {
String te = list.get(i);
}
endTime = System.currentTimeMillis();
result = endTime - starttime;
System.out.println("use get Method traverses the collection:"+result+"millisecond");
}
}
Operation result:
Time taken to traverse the collection using iterator: 6 ms
Time spent traversing the collection using the get method: 2509 milliseconds
Note: Java also provides a dynamic array table class ArrayList with sequential structure. The array table uses sequential structure to store data. Array table is not suitable for dynamically changing its stored data, such as adding and deleting units (slower than linked list). However, because the array table uses the sequential structure to store data, the data in the nth cell in the array table is faster than that in the nth cell in the linked list. Many methods of ArrayList class are similar to LinkedList. The essential difference between them is that one uses sequential structure and the other uses chain structure.
You can use ordinary LinkedList to create a linked list object
LinkedList mylist = new LinkedList();
Then, the mylist linked list can use the add(Object obj) method to add nodes to the linked list in turn. Since any class is a subclass of the Object class, any Object can be used as an Object in the linked list node. It should be noted that when using get() to obtain the Object in a node, the type conversion operator should be used to convert back to the original type. The main purpose of Java generics is to establish a type safe collection framework. The advantage is that when using the data structures established by these generic classes, there is no need for forced type conversion, that is, there is no need for runtime type checking.
import java.util.Iterator;
import java.util.LinkedList;
public class Example13_4 {
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList mylist = new LinkedList();
mylist.add("you"); //The first node in the linked list
mylist.add("good"); //The second node in the linked list
int number = mylist.size(); //Get the length of the linked list
for(int i=0;i<number;i++) {
String temp = (String)mylist.get(i); //The extracted data must be cast
System.out.println("The first"+i+"Data in node:"+temp);
}
Iterator iter = mylist.iterator();
while(iter.hasNext()) {
String te = (String)iter.next();
System.out.println(te);
}
}
}Operation results:
Data in node 0: you
Data in node 1: OK
You
OK
Use object flow to realize the entry and display system of commodity inventory. There is a "commodity" class that implements the interface Serializable. The program takes the object of this class as the linked node, and then writes the linked list to the file.
public class Example13_5 {
public static void main(String[] args) {
// TODO Auto-generated method stub
WindowGoods win = new WindowGoods();
win.setTitle("Entry and display of goods");
}
}
Goods.java
public class Goods implements java.io.Serializable {
String name, mount, price;
public void setName(String name) {
this.name = name;
}
public void setMount(String mount) {
this.mount = mount;
}
public void setPrice(String price) {
this.price = price;
}
public String getName() {
return name;
}
public String getMount() {
return mount;
}
public String getPrice() {
return price;
}
}
InputArea.java
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.LinkedList;
import javax.swing.*;
public class InputArea extends JPanel implements ActionListener {
File f = null; // File for storing linked list
Box baseBox, boxV1, boxV2;
JTextField name, mount, price; // View provided for the Goods object
JButton button; // controller
LinkedList<Goods> goodsList; // Linked list of Goods objects
InputArea(File f) {
this.f = f;
goodsList = new LinkedList<Goods>();
name = new JTextField(12);
mount = new JTextField(12);
price = new JTextField(12);
button = new JButton("Input");
button.addActionListener(this);
boxV1 = Box.createVerticalBox();
boxV1.add(new JLabel("Enter name"));
boxV1.add(Box.createVerticalStrut(8));
boxV1.add(new JLabel("Enter inventory"));
boxV1.add(Box.createVerticalStrut(8));
boxV1.add(new JLabel("Enter unit price"));
boxV1.add(Box.createVerticalStrut(8));
boxV1.add(new JLabel("Click enter"));
boxV2 = Box.createVerticalBox();
boxV2.add(name);
boxV2.add(Box.createVerticalStrut(8));
boxV2.add(mount);
boxV2.add(Box.createVerticalStrut(8));
boxV2.add(price);
boxV2.add(Box.createVerticalStrut(8));
boxV2.add(button);
baseBox = Box.createHorizontalBox();
baseBox.add(boxV1);
baseBox.add(Box.createHorizontalStrut(10));
baseBox.add(boxV2);
add(baseBox);
}
@Override
public void actionPerformed(ActionEvent e) {
// TODO Auto-generated method stub
if (f.exists()) {
try {
FileInputStream fi = new FileInputStream(f);
ObjectInputStream oi = new ObjectInputStream(fi);
goodsList = (LinkedList<Goods>) oi.readObject();
fi.close();
oi.close();
Goods goods = new Goods();
goods.setName(name.getText());
goods.setMount(mount.getText());
goods.setPrice(price.getText());
goodsList.add(goods);
FileOutputStream fo = new FileOutputStream(f);
ObjectOutputStream out = new ObjectOutputStream(fo);
out.writeObject(goodsList);
out.close();
} catch (Exception ee) {
}
} else {
try {
f.createNewFile();
Goods goods = new Goods();
goods.setName(name.getText());
goods.setMount(mount.getText());
goods.setPrice(price.getText());
goodsList.add(goods);
FileOutputStream fo = new FileOutputStream(f);
ObjectOutputStream out = new ObjectOutputStream(fo);
out.writeObject(goodsList);
out.close();
} catch (Exception ee) {
}
}
}
}
ShowArea.java
import java.awt.BorderLayout;
import java.awt.Event;
import java.util.Iterator;
import java.util.LinkedList;
import javax.swing.JPanel;
import javax.swing.JTable;
public class ShowArea extends JPanel {
JTable table;
Object tableElement[][], name[] = { "name", "stock", "Unit Price" };
public ShowArea() {
setLayout(new BorderLayout());
table = new JTable();
add(table);
}
public void show(LinkedList<Goods> goodsList) {
remove(table);
int lenght = goodsList.size();
tableElement = new Object[lenght][3];
table = new JTable(tableElement, name);
add(table);
Iterator<Goods> iter = goodsList.iterator();
int i = 0;
while (iter.hasNext()) {
Goods goods = iter.next();
tableElement[i][0] = goods.getName();
tableElement[i][1] = goods.getMount();
tableElement[i][2] = goods.getPrice();
i++;
}
table.repaint();
}
}
WindowGoods.java
import java.awt.BorderLayout;
import java.awt.CardLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.File;
import java.io.FileInputStream;
import java.io.ObjectInputStream;
import java.util.LinkedList;
import javax.swing.JFrame;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
public class WindowGoods extends JFrame implements ActionListener {
File file = null;
JMenuBar bar;
JMenu fileMenu;
JMenuItem login, show;
InputArea inputMessage; // Input interface
ShowArea showMessage; // Display interface
JPanel pCenter;
CardLayout card;
WindowGoods() {
file = new File("stock.txt"); // File for storing linked list
login = new JMenuItem("Input");
show = new JMenuItem("display");
bar = new JMenuBar();
fileMenu = new JMenu("Menu options");
fileMenu.add(login);
fileMenu.add(show);
bar.add(fileMenu);
setJMenuBar(bar);
login.addActionListener(this);
show.addActionListener(this);
inputMessage = new InputArea(file); // Create entry interface
showMessage = new ShowArea(); // Create display interface
card = new CardLayout();
pCenter = new JPanel();
pCenter.setLayout(card);
pCenter.add("Input", inputMessage);
pCenter.add("display", showMessage);
add(pCenter, BorderLayout.CENTER);
card.show(pCenter, "Input");
setVisible(true);
setBounds(100, 50, 420, 380);
validate();
setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
}
public void actionPerformed(ActionEvent e) {
// TODO Auto-generated method stub
if (e.getSource() == login) {
card.show(pCenter, "Input");
} else if (e.getSource() == show) {
try {
FileInputStream fi = new FileInputStream(file);
ObjectInputStream oi = new ObjectInputStream(fi);
LinkedList<Goods> goodsList = (LinkedList<Goods>) oi.readObject();
fi.close();
oi.close();
card.show(pCenter, "display");
showMessage.show(goodsList);
} catch (Exception ee) {
System.out.println(ee);
JOptionPane.showMessageDialog(this, "No information", "Prompt dialog box", JOptionPane.WARNING_MESSAGE);
}
}
}
}
II stack
Heap is a "last in, first out" data structure, which can only input or output data at one end. The stack places the first data put into the stack at the bottom, and the subsequent data on the top of the existing data. The operation of inputting data into the stack is called "pressing the stack", and the operation of outputting data from the stack is called "bouncing the stack". Since the stack always performs data input / output operations at the top, the pop-up stack always outputs (deletes) the last data pushed into the stack, which is the reason for "last in, first out".
Using Java The stack < E > generic class in util package creates a stack object, which can use "public E push(E item);" Realize stack pressing operation; Use "public E pop();" Realize the spring stack operation; Use "public boolean empty();" Judge whether there is still data in the heap search. If there is data, return false, otherwise return true; Use "public E peek();" Get the data at the top of the stack, but do not delete the data; Use "public int search(Object data);" Gets the position of the data in the stack. The top position is 1, which increases successively downward. If the stack does not contain this data, it returns - 1.
Stack is a very flexible data structure. Using stack can save memory overhead.
For example, recursion is a memory consuming algorithm. Most recursion can be eliminated with the help of the stack to achieve the same purpose as the recursive algorithm. Fibonacci integer sequence is a familiar recursive sequence. Its nth term is the sum of the first two terms, and the first and second terms are 1. The following example 13.6 outputs several items of the recursive sequence with a stack.
import java.util.Stack;
public class Example13_6 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Stack<Integer>stack = new Stack<Integer>();
stack.push(1);
stack.push(1);
int k = 1;
while(k<=10) {
for(int i=1;i<=2;i++) {
int f1 = stack.pop();
int f2 = stack.pop();
int next = f1+f2;
System.out.println(""+next);
stack.push(next);
stack.push(f2);
k++;
}
}
}
}
Operation results:
2
3
5
8
13
21
34
55
89
144