highlight: a11y-dark
This is the 7th day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021
The linear table
Linear tables can be implemented in the following ways
1. The order sheet
The sequential storage of linear tables refers to storing the data elements of linear tables in a contiguous space in memory. The linear tables stored in this way are called sequential tables, and their implementation mainly depends on arrays.
(1) In space:
The implementation of the sequence table is generally to continuously open up a section of space, and then the data is added and deleted, so when we do not know how much data to store, if the space to open up with the sequence table is too large, it will cause a certain degree of waste.
(2) Time: the time complexity of accessing random elements: Since array subscript access is supported, the time complexity of sequential table accessing random elements is O (1).
Time complexity of inserting and deleting elements in random positions: Because the elements of the sequential table are stored continuously, all the elements after it need to be moved back or one element in advance to insert and delete elements in a specific position, which costs a lot of time
Order table implementation:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace_ linear table {// The IComparable
interface defines type-specific common comparison methods implemented by value types or classes to sort actual cases.
public class SelfList<T> where T:IComparable
{
//T GetItem(int index); // Get the value of the index
//void Add(T item); // The method to add elements
//void Insert(int index, T item); // Insert the element method
//void RemoveAt(int index); // Remove the element at the specified index.
//int IndexOf(T item); / / search specified object, and returns the whole System. Collections. Generic. List ` 1 zero-based index of the first match.
//int LastIndexOf(T item); // Searches for the specified object, starting from the index of the first matching item.
//void Sort(); // Sort from smallest to largest
int count;
T[] arry;
public int Count { get=> count; }public int Capacity{ get => arry.Length; }// Capacity for capacity expansion
public SelfList(int size)
{
arry = new T[size];
}
public SelfList()
{
arry = new T[4];// When size is not specified, the default is 4
}
public T GetItem(int index)
{
if (index>=0&&index<Count)
{
return arry[index];
}
else
{
throw new Exception("Index out of range"); }}// Access via indexer
public T this[int index]
{
get
{
return GetItem(index);
}
set
{
if (index >= 0 && index < Count)
{
arry[index] = value;
}
else
{
throw new Exception("Index out of range"); }}}public void Add(T item)
{
if (Count==Capacity)
{
T[] newarry = new T[Count * 2];
Array.Copy(arry, newarry, Count);
arry = newarry;
}
arry[Count] = item;
count++;
}
public void Insert(int index, T item)
{
if (index>=0&&index<=Count)// The last bit can be inserted
{
if (Count == Capacity)
{
T[] newarry = new T[Count * 2];
Array.Copy(arry, newarry, Count);
arry = newarry;
}
for (int i = Count- 1; i >= index; i--)
{
arry[i + 1] = arry[i];
}
arry[index] = item;
count++;
}
else
{
throw new Exception("Index out of range"); }}public int IndexOf(T item)
{
for (int i = 0; i < count; i++)
{
if (arry[i].Equals(item))
{
returni; }}return - 1;
}
public int LastIndexOf(T item)
{
for (int i = Count; i >=0; i--)
{
if (arry[i].Equals(item))
{
returni; }}return - 1;
}
public void RemoveAt(int index)
{
if (index >= 0 && index < Count)
{
for (int i = index; i < count- 1; i++)
{
arry[i - 1] = arry[i];
}
count--;
}
else
{
throw new Exception("Index out of range"); }}CompareTo(Object) must return Int32 with one of the following three values, as shown in the following table.
/ / comment
// Indicates the value
The current instance CompareTo precedes the object specified by the method in the sort order.
The instance and the object specified by the method appear in the same sort order until zero.
// Greater than zero This current instance CompareTo follows the object specified by the method in the sort order.
public void Sort()
{
for (int i = 0; i < Count- 1; i++)
{
for (int j = 0; j < Count-i- 1; j++)
{
if (arry[j].CompareTo(arry[j+1) >0)
{
T tem = arry[j+1];
arry[j+1] = arry[j];
arry[j] = tem;
}
}
}
}
}
}
Copy the codeSingly linked lists
A linked list is a linear list of data elements stored in an arbitrary set of storage units (which can be contiguous or discontiguous). When storing data elements, not only the information of the data element itself, but also the storage address information of its adjacent data elements are stored. These two parts of information constitute the storage image of the data element, which is called Node. The domain that stores the information of the data element itself is called the data domain of the node, and the domain that stores the address information of the data element adjacent to it is called the reference domain of the node.
The diagram below shows the chained storage structure of linear tables (A1, A2, A3, A4, A5, A6).
(1) Spatially: A single linked list is a space that opens only one node at a time, which is used to store the data to be saved and the pointer to the next node or NULL. However, since the space opened each time is not continuous, it is easy to form a fragment space, resulting in a waste of space
(2) Time:
** Time complexity of accessing random elements :** Single linked list data is stored in chain, its elements do not support random access, to know an element, can only be traversed from the beginning of the list until the element is found. So the average time for singly linked lists to access random elements is O (n).
The time complexity of inserting and deleting elements at random positions: when inserting or deleting elements in a single linked list, it only needs to change its precursor node and the orientation of inserting or deleting elements. Therefore, the time complexity of inserting and deleting elements at random positions in a single linked list is O (1).
Chain list implementation
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace_ linear table {/// <summary>
///Linked list (one-way linked list)
/// </summary>
class Chain<T> where T:IComparable
{
//T GetItem(int index); // Get the value of the index
//void Add(T item); // The method to add elements
//void Insert(int index, T item); // Insert the element method
//void RemoveAt(int index); // Remove the element at the specified index.
//int IndexOf(T item); / / search specified object, and returns the whole System. Collections. Generic. List ` 1 zero-based index of the first match.
//int LastIndexOf(T item); // Searches for the specified object, starting from the index of the first matching item.
//void Sort(); // Sort from smallest to largest
int count;
Node<T> head;
public Chain()
{
head = null;
}
public int Count { get => count; }
public T GetItem(int index)
{
if (index >= 0 && index < Count)
{
Node<T> temp = head;
for (int i = 1; i <= index; i++)
{
temp = temp.next;
}
return temp.deta;
}
else
{
throw new Exception("Index out of range"); }}// Access via indexer
public T this[int index]
{
get
{
return GetItem(index);
}
set
{
if (index >= 0 && index < Count)
{
Node<T> temp = head;
for (int i = 0; i < index; i++)
{
temp = temp.next;
}
temp.deta = value;
}
else
{
throw new Exception("Index out of range"); }}}public void Add(T item)
{
Node<T> newnode = new Node<T>(item);
if (head==null)
{// The first node is the head node
head = newnode;
}
else
{// Place the new node at the end of the list when the first node is not the head node
Node<T> temp = head;
while(temp.next! =null)
{
temp = head.next;
}
temp.next = newnode;
}
count++;
}
public void Insert(int index, T item)
{
Node<T> newnode = new Node<T>(item);
if (index == 0)
{// Insert position is the first node
head= newnode;
newnode.next = head.next;
}
else
{// If the insertion position is not the first node, get the node of the insertion position (currentNode) and the node before the insertion position (preNode),
// insert preNode to newNode (newNode), newNode (newNode) to insert node (currentNode)
Node<T> temp = head;
for (int i = 1; i <= index- 1; i++)
{
temp = temp.next;
}
Node<T> preNode = temp;
Node<T> currentNode = temp.next;
temp.next = newnode;
newnode.next = currentNode;
}
count++;
}
public int IndexOf(T item)
{
Node<T> temp = head;
int index = 0;
while(temp! =null)
{
if (temp.deta.Equals(item))
{
return index;
}
index++;
temp = temp.next;
}
return - 1;
}
public int LastIndexOf(T item)
{
Node<T> temp = head;
int index = 0;
T[] array = new T[Count];
while(temp ! =null)
{
array[index++] = temp.deta;
temp = temp.next;
}
for (int i = index- 1; i >=0; i++)
{
if (array[i].Equals(item))
{
returni; }}return - 1;
}
public void RemoveAt(int index)
{
if (index == 0)
{// Remove the first node
head = head.next;
}
else
{// Select preNode (nextNode) and nextNode (nextNode).
// Set preNode (nextNode) to nextNode (nextNode)
Node<T> temp = head;
for (int i = 1; i <= index - 1; i++)
{
temp = temp.next;
}
Node<T> preNode = temp;
Node<T> nextNode = temp.next.next;
preNode.next = nextNode;
}
count--;
}
public void Sort()
{
// Get all node positions
Node<T> temp = head;
Node<T>[] detas = new Node<T>[Count];
for (int i = 0; i < Count; i++)
{
detas[i] = temp;
temp = temp.next;
}
// Bubble sort
for (int i = 0; i < Count - 1; i++)
{
for (int j = 0; j < Count - i - 1; j++)
{
if (detas[j].deta.CompareTo(detas[j+1].deta)>0)
{
T temdeta = detas[j].deta;
detas[j].deta = detas[j + 1].deta;
detas[j+1].deta = temdeta;
}
}
}
}
}
}
Copy the code