Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java implementation linear table - represents the order of representation and chain     - Linux GCC 5.1.0 compiler installation (Linux)

- Ubuntu 14.10 users to install Audio Recorder 1.5.7 (Linux)

- How to download video youtube-dl in Linux (Linux)

- VMWare virtual machine without rebooting way to add virtual disk (Linux)

- OpenGL Superb Learning Notes - Depth Texture and Shadows (Programming)

- Zabbix configuration external network mail alarm (Server)

- Use mod_wsgi Django application deployment (Server)

- Analysis of Java keyword final (Programming)

- VPS xen openvz kvm (Server)

- How to add and delete bookmarks in Ubuntu (Linux)

- Bash command substitution (Programming)

- Ubuntu 14.04 build Android 5.1 development environment and compiler (Linux)

- Ubuntu 14.04, 13.10 install OpenCV 2.4.9 (Linux)

- Sort sql MySQL 5.6 upgrade slow Cause Analysis (Database)

- Basic Tutorial: Linux novice should know 26 commands (Linux)

- C # / iOS / Android Universal Encryption and decryption (Programming)

- Firewall types and instructions (Linux)

- Apache site default home page settings (Server)

- Expert advice: Do not use the computer security IE browser (Linux)

- Java data structures - the linear form of the single-chain applications (Programming)

 
         
  Java implementation linear table - represents the order of representation and chain
     
  Add Date : 2017-08-31      
         
       
         
  Comparative sequence showing and chain represented by:

1. write mode: sequential access sequence table can be a random access; access list elements can only order from the head of the table;

2. Logical structure and physical structure: When stored sequentially, logically-adjacent elements of the corresponding physical storage location is also adjacent; chain store, the logically-adjacent elements, the physical storage locations are not necessarily adjacent;

3. Locate, insert and delete operations:

Find by value, when the linear form in the case of disorder, are both time complexity o (n); and when the order table ordered, binary search can be used, then the time complexity is o (log n );

Bitwise find, order table supports random access, time complexity is o (1); and the average time complexity of the list is o (n).

Insertion and deletion sequence table moving average of half a meter long elements; the list is inserted, deleted, simply modify the pointer to the relevant node.

4. Space allocation: sequential storage generally static storage allocation based on a single storage space is full it can not expand; node linked storage space only when needed to apply for assignment, as long as there is enough memory space can be allocated.

Sequentially illustrating implementation:

public class ArrayList < E> {
    final int defaultSize = 0;
    // Maximum length linear form; int maxSize
    // Current length of the linear form; int length
    Object [] arrayList; // array storage linear table
    
    / *
    * Constructor
    * /
    public ArrayList (int size) {
        initList (size);
    }
    
        // A 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];
        }
    }

        // Table length
    public int length () {
        return length;
    }

        // Find by value
    public int locateElem (Object e) {
        for (int i = 0; i < length; i ++) {
            if (arrayList [i] == e) {
                return i;
            }
        }
        return -1;
    }

        // Bitwise Find
    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 ( "new elements into the wrong location:" + i);
        }
        if (i> = maxSize) {
            throw new RuntimeException ( "sequence table is full, you can not insert a new element");
        }
        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 ( "position of the element to be deleted in error:" + i);
        }
        if (length == 0) {
            throw new RuntimeException ( "sequence table is empty, you can not remove elements");
        }
        for (int j = i; j < length-1; j ++) {
            arrayList [j] = arrayList [j + 1];
        }
        arrayList [length-1] = "";
        length--;
    }

      // Empty sentence
    public boolean isEmpty () {
        ? Return length == 0 true: false;
    }

        // Delete the order form
    public void destroyList () {
        this.arrayList = null;
        this.length = 0;
        this.maxSize = 0;
    }
}

Single list represents the realization of:

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; // the head node
    int size = 0; // list size
    
    public LinkedList () {
        this.header = new Node < E> ();
    }

    // Get the length of the list
    public int length () {
        return size;
    }

    // Find the node by value, return to the node's position
    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 the first index node locations
    public Node < E> getNode (int index) {
        if (index> size || index < 0) {
            throw new RuntimeException ( "index values are wrong:" + index);
        }
        Node < E> temp = new Node < E> ();
        temp = header;
        int count = 1;
        while (count! = index) {
            temp = temp.next;
            count ++;
        }
        return temp;
    }

    // Last added
    public boolean addToLast (E e) {
        if (size == 0) {
            header.e = e;
        } Else {
            Node < E> newnode = new Node < E> (e); // add content package required for the node
            Node < E> last = getNode (size); // get the last node
            last.next = newnode;
        }
        size ++;
        return true;
    }
    
    // Add head
    public boolean addTofirst (E e) {
        if (size == 0) {
            header.e = e;
        } Else {
            Node < E> newnode = new Node < E> (e); // add content package required for the node
            newnode.next = header.next;
            header.next = newnode;
        }
        size ++;
        return true;
    }

    // Inserted into the index th position
    public boolean insert (int index, E e) {
        Node < E> newnode = new Node < E> (e); // add content package required for the node
        Node < E> cnode = getNode (index-1); // get the first index-1 node
        newnode.next = cnode.next;
        cnode.next = newnode;
        size ++;
        return true;
    }

    // Delete the first index node
    public boolean delete (int index) {
        Node < E> prinode = getNode (index-1); // get the previous node was deleted node
        Node < E> delnode = prinode.next; // get removed node
        prinode.next = delnode.next;
        size -;
        return true;
    }

    // Empty sentence
    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 ();
    }
}

Dual representation list

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; // the head node
    int size = 0; // list size
    
    public DoubleLinkedList () {
        this.header = new TNode < E> ();
    }
    
    // Last added
    public boolean addToLast (E e) {
        if (size == 0) {
            header.e = e;
        } Else {
            TNode < E> TNode = new TNode < E> (e); // add content package required for the node
            TNode < E> last = getNode (size); // get the last node
            last.next = TNode;
            TNode.prior = last;
        }
        size ++;
        return true;
    }
    
    
    // Find the first index node locations
    public TNode < E> getNode (int index) {
        if (index> size || index < 0) {
            throw new RuntimeException ( "index values are wrong:" + index);
        }
        TNode < E> temp = new TNode < E> ();
        temp = header;
        int count = 1;
        while (count! = index) {
            temp = temp.next;
            count ++;
        }
        return temp;
    }
    
    // Inserted into the index th position
    public boolean insert (int index, E e) {
        TNode < E> TNode = new TNode < E> (e);
        TNode < E> cnode = getNode (index-1); // find the first index-1 node locations
        TNode.next = cnode.next;
        TNode.prior = cnode;
        cnode.next.prior = TNode;
        cnode.next = TNode;
        size ++;
        return true;
    }
    
    // Delete the first index node
    public boolean delete (int index) {
        TNode < E> delnode = getNode (index);
        delnode.prior.next = delnode.next;
        delnode.next.prior = delnode.prior;
        size--;
        return true;
    }
}
     
         
       
         
  More:      
 
- Some practical tips Linux (Linux)
- Linux Basics Tutorial: Combining awk delete data before the specified date hdfs (Linux)
- Linux Quick Install MongoDB (Database)
- OpenSIPS offline messaging feature set (Server)
- C # assembly calls across constants, variables and functions (Programming)
- Linux Security Setup Guide (Linux)
- Efficient Linux Shell - Shell special characters Summary (Linux)
- Linux file time Comments ctime mtime atime (Linux)
- MariaDB 10.0.X, the dynamic column support JSON format to obtain data (Database)
- The three-way division of the sorting algorithm Quicksort (Programming)
- Install Debian Linux with R on the Android system (Linux)
- Linux, Eclipse flash back and reinstall the JDK methods (Linux)
- Several configuration changes illustrate deployment of PHP (Server)
- C ++ constant definition (Programming)
- Some common regular expressions (Linux)
- Redhat 5 prohibit IPv6 (Linux)
- MySQL composite partition (Database)
- MySQL primary and secondary replicate data inconsistencies (Database)
- The compiler installed Kaldi under Ubuntu 12.04 (Linux)
- Security basics: simple analytical framework for Linux system firewall (Linux)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.