Java Implement linear table – Sequential representation and chain representation （java）

A comparison between sequential representation and chained representation ：

1. How to read and write ： A sequence table can be accessed sequentially , It can also be accessed randomly ; A linked list can only access elements sequentially from the header ;

2. Logical structure and physical structure ： When storing in sequence , Logically adjacent elements have their corresponding physical storage locations adjacent ; Chain storage , Logically adjacent elements , Its physical storage location is not necessarily adjacent ;

3. lookup 、 Insert and delete operations ：

According to the value lookup , When a linear table is out of order , The time complexity of both is o(n); And when the sequence table is in order , You can use half to find , At this time, the time complexity is o(log n);

Search by bit , Sequential tables support random access , The time complexity is o(1); The average time complexity of the linked list is o(n).

The insert and delete operations of sequential tables need to move elements of half a table length on average ; Insertion of linked list 、 Delete operation , Just modify the pointer of the relevant node .

4. Space allocation ： Sequential storage is usually based on static storage allocation , When a single storage space is full, it cannot be expanded ; The node space of chain storage can only be allocated when needed , As long as the memory has enough space to allocate .

The order sheet The realization of ：

public class ArrayList<E> {
final int defaultSize=0;
int maxSize; // The maximum length of a linear table
int length; // Linear meter current length
Object[] arrayList; // An array of linear tables
/*
* Constructors
*/
public ArrayList(int size){
initList(size);
}
// As given size Initialization sequence table
public void initList(int size) {
if(size < 0){
throw new RuntimeException(" Array size error ：" + size);
}else{
this.maxSize= size;
this.length=0;
this.arrayList = new Object[size];
}
}
// Long table
public int length() {
return length;
}
// According to the value lookup
public int locateElem(Object e) {
for(int i=0 ;i<length;i++){
if(arrayList[i] == e){
return i;
}
}
return -1;
}
// Search by bit
public Object getElem(int i) {
if(i<0 || i>=length ){
throw new RuntimeException(" Parameter error ："+i);
}
if(length ==0){
throw new RuntimeException(" Sequence table is empty ");
}
return arrayList[i];
}
// Insert
public void insert(int i, Object e) {
if(i<0 || i>length+1 ){
throw new RuntimeException(" The new element is inserted in the wrong position ："+i);
}
if(i >= maxSize){
throw new RuntimeException(" The sequence table is full , You can't insert new elements ");
}
for(int j=length;j<i; j--){
arrayList[j]=arrayList[j-1];
}
arrayList[i]=e;
length++;
}
// Delete
public void delete(int i, Object e) {
if(i<0 || i > length-1){
throw new RuntimeException(" The position of the element to be deleted is wrong ："+i);
}
if(length == 0){
throw new RuntimeException(" Sequence table is empty , Cannot delete element ");
}
for(int j=i;j<length-1;j++){
arrayList[j] = arrayList[j+1];
}
arrayList[length-1]="";
length--;
}
// Sentenced to empty
public boolean isEmpty() {
return length==0 ? true : false;
}
// Delete order table
public void destroyList() {
this.arrayList=null;
this.length=0;
this.maxSize=0;
}
}

  Single chain list The implementation of representation ：

class Node<E>{
E e; // data
Node<E> next; // Next node
Node(){}
Node(E e){
this.e = e;
this.next = null;
}
}
public class LinkedList<E> {
private Node<E> header = null; // Head node
int size=0; // Chain table size
public LinkedList() {
this.header = new Node<E>();
}
// Get the length of the list
public int length() {
return size;
}
// Find nodes by value , Returns the location of the node
public int locateElem(E e) {
Node<E> temp = header;
int count = 1;
while(temp.next != null && temp.e != e){
temp = temp.next;
count ++;
}
return count;
}
// Find No index Nodes in locations
public Node<E> getNode(int index) {
if(index > size || index < 0){
throw new RuntimeException(" Wrong value has index ：" + index);
}
Node<E> temp = new Node<E>();
temp = header;
int count=1;
while(count != index){
temp = temp.next;
count ++;
}
return temp;
}
// Add at the end
public boolean addToLast(E e) {
if(size == 0){
header.e = e;
}else{
Node<E> newnode = new Node<E>(e); // The content added as needed is encapsulated as nodes
Node<E> last = getNode(size); // Get the last node
last.next = newnode;
}
size ++;
return true;
}
// Head add
public boolean addTofirst(E e) {
if(size == 0){
header.e = e;
}else{
Node<E> newnode = new Node<E>(e); // The content added as needed is encapsulated as nodes
newnode.next = header.next;
header.next = newnode;
}
size ++;
return true;
}
// Insert into index The position of
public boolean insert(int index, E e) {
Node<E> newnode = new Node<E>(e); // The content added as needed is encapsulated as nodes
Node<E> cnode = getNode(index-1); // Get the first index-1 Nodes
newnode.next = cnode.next;
cnode.next = newnode;
size++;
return true;
}
// Delete the first index Nodes
public boolean delete(int index) {
Node<E> prinode = getNode(index-1); // Get the previous node of the deleted node
Node<E> delnode = prinode.next; // Get the deleted node
prinode.next = delnode.next;
size --;
return true;
}
// Sentenced to empty
public boolean isEmpty() {
return size==0 ? true : false;
}
public void destroyList() {
header = null;
size = 0;
}
// Output
public String toString(){
StringBuilder s = new StringBuilder("[");
Node<E> temp = header;
for(int i=0; i < size;i++){
s.append(temp.e.toString()+" ");
temp = temp.next;
}
s.append("]");
return s.toString();
}
}

Double linked list The implementation of representation

class TNode<E>{
E e;
TNode<E> prior, next;
TNode(){}
TNode(E e){
this.e = e;
prior = null;
next = null;
}
}
public class DoubleLinkedList<E> {
private TNode<E> header = null; // Head node
int size=0; // Chain table size
public DoubleLinkedList(){
this.header = new TNode<E>();
}
// Add at the end
public boolean addToLast(E e) {
if(size == 0){
header.e = e;
}else{
TNode<E> TNode = new TNode<E>(e); // The content added as needed is encapsulated as nodes
TNode<E> last = getNode(size); // Get the last node
last.next = TNode;
TNode.prior=last;
}
size ++;
return true;
}
// Find No index Nodes in locations
public TNode<E> getNode(int index){
if(index > size || index < 0){
throw new RuntimeException(" Wrong value has index ：" + index);
}
TNode<E> temp = new TNode<E>();
temp = header;
int count =1;
while(count != index){
temp = temp.next;
count ++;
}
return temp;
}
// Insert into index The position of
public boolean insert(int index,E e){
TNode<E> TNode = new TNode<E>(e);
TNode<E> cnode = getNode(index-1); // Find No index-1 Nodes in locations
TNode.next=cnode.next;
TNode.prior = cnode;
cnode.next.prior = TNode;
cnode.next = TNode;
size++;
return true;
}
// Delete the first index Nodes
public boolean delete(int index){
TNode<E> delnode = getNode(index);
delnode.prior.next=delnode.next;
delnode.next.prior= delnode.prior;
size--;
return true;
}
}

Reference blog ：

https://www.cnblogs.com/CherishFX/p/4607663.html