Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java implementation linear table - represents the order of representation and chain     - Lua non-blocking write log (Programming)

- PL / SQL in forall simple test (Database)

- ORA-14400: inserted partition key does not map to any partition (Database)

- Linux environment variable configuration and save places (Linux)

- Use the vi text editor and copy and paste Linux tips (Linux)

- Build and verify MongoDB3.0.7 version (shard + replica) Cluster (Database)

- Ubuntu installed Komodo editor by PPA (Linux)

- Mounting Windows shared directory system under the Linux (Linux)

- Let the router be your security barrier against external attack (Linux)

- Java annotations entry automatically generates SQL statements (Programming)

- To create a Linux server network security (Linux)

- PULL operation mechanism parsing XML Comments (Programming)

- Mac OS X systems create Ubuntu USB boot disk for the Mac (Linux)

- C # asynchronous delegates (Programming)

- CentOS7 install JDK (Linux)

- Linux operating system Samba server configuration and use (Server)

- A step by step teach have to install multi-node cluster configuration Hadoop (Server)

- PXE + Kickstart automatically install CentOS 6.5 (Linux)

- VMware ghost Linux card error (Linux)

- How do I cancel (almost) any operations in Git, (Linux)

 
         
  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:      
 
- MySQL uses mysqld_multi to deploy stand-alone multi-instance detail procedures (Database)
- Using FTPClient to upload and download files in Java (Programming)
- Linux System Getting Started Learning: compile and install ixgbe driver in Ubuntu or Debian (Linux)
- C ++ hash function (Programming)
- Ubuntu15 core CLR (Server)
- Three methods easy data encryption on Linux (Linux)
- Chkconfig command Detailed service is added and shut down the system in two ways to start service under Linux (Linux)
- PostgreSQL export table structure information (Database)
- Linux Network Analysis Tcpdump Command Guide (Linux)
- Linux + Apache + PHP + Oracle based environment to build (Server)
- Installation and Configuration OpenVPN server and client on Ubuntu 15.04 (Server)
- Linux Tutorial: Open multiple tabs in the GNOME terminal in Ubuntu 15.04 (Linux)
- Ubuntu 14.04.02 LTS startup items erroneous writing / dev / sda1 (win 7 loader) Repair (Linux)
- Rails 4.1.6 start being given Could not find a JavaScript runtime (Linux)
- Revised OpenJDK Java Memory Model (Programming)
- ARM Linux system call (Linux)
- Oracle partition table data migration, process management automation (Database)
- Java memory area Explanation (Programming)
- How to use Linux iptables tool for network sharing (Linux)
- The simple multi-threaded Python (Programming)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.