Blog home page (4 messages) Xiao Wu_ Xiao Wu has an idea_ CSDN blog - notes, java,leetcode domain bloggers
Welcome to pay attention
give the thumbs-up
Collection and message
Heaven rewards diligence. Diligence can make up for weakness. Come on with Xiao Wu
17-year-old freshman, limited level, please give advice, thank you very much! - Refer to the book algorithm 4 and learn the video: Dark horse programmer Java data structure and Java algorithm, the most complete data structure + algorithm tutorial of the whole network, 154 Java data structure diagrams_ Beep beep beep_ bilibili
catalogue
One way linked list code implementation
Linear table
Linear table is the simplest, most basic and most commonly used data structure. A linear table is a finite sequence of n data elements with the same characteristics. (a row of people of different heights)
Precursor element: if A is in front of B, A is called the precursor element of B
Successor element: if B is behind a, B is called the successor element of A
Characteristics of linear table:
- The first data element has no precursor. This data element is called "header node"
- The last data element has no successor. This data element is called "tail node"
- Except for the first and last data elements, other data elements have and have only one prefix and suffix
The linear table is defined in mathematical language and can be expressed as (A1,,, ai-1, ai, ai+1,,, an). ai-1 is the precursor element of ai and ai+1 is the successor element of ai
According to the different storage methods of data in the linear table, the linear table can be divided into sequential list and linked list
Sequence table
The sequential table is a linear table saved in the form of an array in the computer memory. The sequential storage of the linear table refers to the sequential storage of each element in the linear table with a group of storage units with continuous addresses, so that the data elements ringing in the logical structure in the linear table are stored in the adjacent physical storage units, That is, the logical adjacency relationship between data elements is reflected through the adjacency relationship physically stored by data elements
| 11 | 32 | 65 | 14 | 32 | 22 | 14 | 8 | 12 |
0 1 2 3 4 5 6 7 8
An array like this is easy to understand
Code implementation of sequence table:
code implementation
public class SequenceList<T> {
//An array of storage elements
private T[] a;
//Record the number of elements in the sequence table
private int N;
//Construction method
public SequenceList(int capacity)
{ //Initialize array
this.a=(T[])new Object[capacity];
this.N=0;
}
//Set a linear table as an empty table
public void reset() {
this.N=0;
}
//Judge whether the current linear table is empty
public boolean isEmpty()
{
return N==0;
}
//Gets the length of the linear table
public int length()
{
return N;
}
//Gets the element at the specified location
public T get(int i)
{
return a[i];
}
//Add element to linear table
public void insert(T t)
{
a[N++]=t;
}
//Insert element t at element i
public void insert(int i,T t)
{
//First, move the element at the i index and the element at the subsequent index backward by one bit
for(int index=N-1;index>i;index--)
{
a[index]=a[index-1];
}
//Then put the t element at the i element
a[i]=t;
}
//Deletes the element at the specified location i and returns the element
public T remove(int i)
{
//Record the value at index i
T current=a[i];
//The elements behind index i can be moved forward one bit in turn
for(int index= i;index<N-1;index++)
{
a[index]=a[index+1];
}
N--;
return current ;
}
//Find where the t element first appears
public int indexOf(T t)
{
for(int i=0;i<N;i++)
{
if(a[i]==t)
{
return i;
}
}
return -1;
}
public static void main(String[] args)
{
//Create sequence table object
SequenceList<String>s =new SequenceList<>(10);
//Test insertion
s.insert("Yao Ming");
s.insert("Xiao Ming");
s.insert("Xiao Wang");
s.insert(1,"Kobe");
//Test acquisition
String gets=s.get(1);
System.out.println("The result at index 1 is:"+gets);
//Test delete
String removeresult =s.remove(0);
System.out.println("The deleted element is:"+removeresult);
//Test empty
s.reset();
System.out.println("The number of elements after emptying is:"+s.length());
}
}
Time complexity
- get(i): the corresponding element can be obtained at one time, and the time complexity is O(1);
- Insert (int i, t, t): every time you insert, you need to move the element after I. the larger N is, the more elements will be moved, and the time complexity is O(N);
- remove(int i): every time you delete, you need to move the elements behind position I once. As the amount of data N increases, more elements are moved, and the time complexity is O(N);
- Since the bottom layer of the sequence table is implemented by an array, and the length of the array is fixed, the container expansion operation is involved in the process of operation. This will lead to the time complexity of the sequence table in the use process is not linear. At some nodes that need to be expanded, the time will increase sharply, especially the more elements, the more obvious
Linked list
Definition: a linked list is a recursive data structure. It is either empty (null), or a node containing generic elements and a reference to another linked list.
Linked list is a discontinuous and non sequential storage structure on the physical storage unit. Its physical structure can not intuitively represent the logical order of data elements. The logical order of data elements is realized through the pointer link order in the linked list. The linked list consists of a series of nodes (each element in the linked list is called a node), which can be generated dynamically at run time.
We can design a class to describe the node, use one attribute to describe the element stored in the node, and use another attribute to describe the next node of the node.
| Class name | Node<T> |
| Construction method | Node (T, node next): creates a node object |
| Member variable | T item: store data Node next: points to the next node |
public class Node<T> {
//Storage element
public T item;
//Point to the next node
public Node next;
public Node(T item,Node next)
{
this.item=item;
this.next=next;
}
public static void main(String[] args)
{
//Build node
Node<Integer>first=new Node<Integer>(10,null);
Node<Integer>second=new Node<Integer>(20,null);
Node<Integer>third=new Node<Integer>(30,null);
//Generate linked list
first.next=second;
second.next=third;
}
}
Unidirectional linked list
Unidirectional linked list is a kind of linked list. It is composed of multiple nodes. Each node is composed of a data field and a pointer field. The data field is used to store data and the pointer field is used to point to its subsequent nodes. The data field of the head node of the linked list does not store data, and the pointer field points to the first node that really stores data.
One way linked list code implementation
import java.util.Iterator; //The Iterable interface is used to iterate over the surface
public class LinkList<T> implements Iterable<T> {
//Record header node
private Node head;
//Record the length of the linked list
private int N;
//Node class
private class Node{
//Store data
T item;
//Next node
Node next;
public Node(T item,Node next)
{
this.item=item;
this.next=next;
}
}
public LinkList() {
//Create knot node
this.head=new Node(null,null);
//Number of initialization elements
this.N=0;
}
//Empty linked list
public void clear()
{
head.next=null;//Make the head node not point to the next node
this.N=0;
}
//Get the length of the linked list
public int length()
{
return N;
}
//Determine whether the linked list is empty
public boolean isEmpty()
{
return N==0;
}
//Gets the element at the specified location i
public T get(int i)
{
//Through the loop, start from the node and look back, i times in turn, you can find the corresponding element
Node n=head.next;//Keep changing n backward until it changes to the ith position
for(int index=0;index<i;index++)
{
n=n.next;
}
return n.item;
}
//Add element t to linked list
public void insert(T t)
{
//Find the last current node
Node n=head;
while(n.next!=null)
{
n=n.next;
}
//Create a new node and save the element t
Node newNode =new Node(t,null);
//Make the current last node point to the new node
n.next=newNode;
//Number of elements plus 1
N++;
}
//Add the element t to the specified location i
public void insert(int i,T t)
{
//Find the node before i position
Node p=head;
for(int index=0;index<=i-1;index++)
{
p=p.next;
}
//Find node at i location
Node c=p.next;
//Create a new node, and the new node needs to point to the node at the original i location
Node newNode =new Node(t,c);
//The previous node in the original i position can point to the new node
p.next=newNode;
//Number of elements + 1
N++;
}
//Deletes the element at the specified position i and returns the deleted element
public T remove(int i)
{
//Find the previous node at position i
Node p=head;
for(int index=0;index<=i-1;i++)
{
p=p.next;
}
//To find the node at i position
Node c=p.next;
//Find the next node at position i
Node nextNode=c.next;
//The previous node points to the next node
p.next=nextNode;
//Number of elements minus 1
N--;
return c.item;
}
//Find the position where the element t first appears in the linked list
public int indexOf(T t)
{
//From the beginning, find each node in turn, take out the item, and compare it with t. If it is the same, it will be found
Node n=head;
for(int index=0;n.next!=null;index++)
{
n=n.next;
if(n.item==t)
return index;
}
return -1;
}
public Iterator<T> iterator()
{
return new LIterator();
}
private class LIterator implements Iterator{
private Node n;
public LIterator()
{
this.n=head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next()
{
n=n.next;
return n.item;
}
}
}
import java.util.Arrays;
public class test{
public static void main(String[] args)
{
//Create a one-way linked list object
LinkList <String> s1= new LinkList<>();
//Test insertion
s1.insert("Yao Ming");
s1.insert("Kobe");
s1.insert("Xiao Wang");
s1.insert(1,"Jackie Chan");
for(String s:s1)
{
System.out.println(s);
}
System.out.println("--------------------------");
//Test acquisition
String getresult =s1.get(1);
System.out.println("Get result at index 1 is:"+getresult);
//Test delete
String removeresult =s1.remove(0);
System.out.println("Delete element is:"+removeresult);
//Test empty
s1.clear();
System.out.println("The number of elements in the cleared linear table is:"+s1.length());
}
}
Bidirectional linked list
Definition: a two-way linked list, also known as a two-way list, is a kind of linked list. It is composed of multiple nodes. Each node is composed of a data field and two pointer fields. The data field is used to store data, one pointer field is used to point to its successor nodes, and the other pointer field is used to refer to the forward driving nodes. The data field of the head node of the linked list does not store data, the pointer field value pointing to the predecessor node is null, and the pointer field pointing to the successor node points to the first node that actually stores data.
Code implementation
import java.util.Iterator;
//The Iterable interface is used to iterate over the surface
public class TowWayLinkList<T> implements Iterable<T> {
//First node
private Node head;
//Tail node
private Node last;
//Length of linked list
private int N;
//Node class
private class Node{
//Store data
public T item;
//Point to previous node
public Node pre;
//Point to the next node
public Node next;
public Node(T item,Node pre,Node next)
{
this.item=item;
this.next=next;
this.pre=pre;
}
}
public TowWayLinkList()
{
//Initialize head and tail nodes
this.head=new Node(null,null,null);
this.last=null;//At the beginning, the tail node has no data
//Number of initialization elements
this.N=0;
}
//Empty linked list
public void clear()
{
this.head.next=null;
this.head.item=null;
this.head.pre=null;
this.last=null;
this.N=0;
}
//Get linked list length
public int length()
{
return N;
}
//Determine whether the linked list is empty
public boolean isEmpty()
{
return N==0;
}
//Get the first element
public T getFirst()
{ if(isEmpty())
{
return null;
}
return head.next.item;
}
//Get the last element
public T getLast()
{
if(isEmpty())
{
return null;
}
return last.item;
}
//Insert element t
public void insert(T t)
{
//If the linked list is empty, 1 Create a new node, 2 And let the new node become the tail node, 3 And let the head node point to the new node
if(isEmpty())
{
//1. Create a new node
Node newNode=new Node(t,head,null);
//2. Make the new node the tail node
last=newNode;
//3. Make the head node point to the new node
head.next=last;
}
else//If the linked list is not empty
{
//Create a new node
Node oldlast=last;
Node newNode=new Node(t,oldlast,null);
//Make the current tail node point to the new node
oldlast.next=newNode;
//Let the new node be called the tail node
last=newNode;
}
N++;//Number of elements plus 1
}
//Inserts the element t at the specified location i
public void insert(int i,T t)
{
//Find the previous node at position i
Node pre=head;
for(int index=0;index<=i-1;index++)
{
pre=pre.next;
}
//Find the node at position i
Node c=pre.next;
//Create a new node
Node newNode=new Node(t,pre,c);
//Let the next node of the previous node at i position become a new node
pre.next=newNode;
//Make the previous node at i position become a new node
c.pre=newNode;
//Number of elements + 1
N++;
}
public T get(int i)
{
Node n=head.next;
for(int index=0;index<i;index++)
{
n=n.next;
}
return n.item;
}
//Find the position where the element t first appears in the linked list
public int indexOf(T t)
{
//From the beginning, find each node in turn, take out the item, and compare it with t. If it is the same, it will be found
Node n=head;
for(int index=0;n.next!=null;index++)
{
n=n.next;
if(n.item==t)
return index;
}
return -1;
}
//Deletes the element at the specified position i and returns the deleted element
public T remove(int i)
{
//Find the previous node at position i
Node pre=head;
for(int index=0;index<=i-1;i++)
{
pre=pre.next;
}
//To find the node at i position
Node c=pre.next;
//Find the next node at position i
Node nextNode=c.next;
//Let the next node of the previous node of i position become the next node of i position
pre.next=nextNode;
//Let the previous node of the last node in i position become the previous node in i position
nextNode.pre=pre;
//Number of elements minus 1
N--;
return c.item;
}
@Override
public Iterator<T> iterator() {
// TODO Auto-generated method stub
return new TIterator();
}
private class TIterator implements Iterator{
private Node n;
public TIterator()
{
this.n=head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next()
{
n=n.next;
return n.item;
}
}
}import java.util.Arrays;
public class test{
public static void main(String[] args)
{
//Create a two-way linked list object
TowWayLinkList <String> s1= new TowWayLinkList<>();
//Test insertion
s1.insert("Yao Ming");
s1.insert("Kobe");
s1.insert("Xiao Wang");
s1.insert(1,"Jackie Chan");
for(String s:s1)
{
System.out.println(s);
}
System.out.println("-------------------------");
System.out.println("The first element is"+s1.getFirst());
System.out.println("The last element is"+s1.getLast());
System.out.println("--------------------------");
//Test acquisition
String getresult =s1.get(1);
System.out.println("Get result at index 1 is:"+getresult);
//Test delete
String removeresult =s1.remove(0);
System.out.println("Delete element is:"+removeresult);
//Test empty
s1.clear();
System.out.println("The number of elements in the cleared linear table is:"+s1.length());
}
}
Time complexity analysis
Video notes:
- get(int i): for each query, you need to start from the head of the linked list and search backward in turn. As the number of data elements N increases, the more elements are compared, and the time complexity is O(n)
- Insert (int i, t, t): for each insertion, you need to find the previous element at position I first, and then complete the insertion operation. With the increase of data element N, the more elements to find, and the time complexity is O(n)
- remove(int i): for each removal, you need to find the previous element at position I first, and then complete the insertion operation. As the number of data elements N increases, the more elements to find, and the time complexity is O(n)
- Compared with the sequential list, the insertion and deletion time complexity of the linked list is the same, but it still has great advantages, because the physical address of the linked list is discontinuous, it does not need to specify the size of storage space in advance, or it involves operations such as capacity expansion in the storage process, and it does not involve the exchange of elements
- Compared with the sequential list, the query performance of the linked list will be lower. Therefore, if there are many query operations in our program, it is recommended to use sequential list, add and delete operations are more, and it is recommended to use linked list
Learning is like sailing against the current. Come on with Xiao Wu!