Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java implementation linear table - represents the order of representation and chain     - Installation in lxml Python module (Linux)

- Linux hard drive failure Case Studies (Linux)

- Use the TC flow control test under Linux (Linux)

- Features and prevention methods elaborate network security grayware (Linux)

- Installation and use of Linux Sniffer tool Tcpdump (Linux)

- Oracle JDK installation under Ubuntu Linux (Linux)

- Java collections series (Programming)

- CentOS7 Kubernetes used on container management (Server)

- Compression software on a simple comparison of zip and gz (Linux)

- On the PC goes heavy security watch your startup items (Linux)

- CentOS 5.8 (64) Python 2.7.5 installation error resolved (Linux)

- 10 practical Java programming technology (Programming)

- The Zabbix2.4.5 source compiler installation under Ubuntu 14.04 (Server)

- CentOS 6.5 installation and simple configuration Nginx (Server)

- How to ensure that the Internet will not be attacked (Linux)

- Nodejs complete installation instructions for Express (Linux)

- Linux console password solution (Programming)

- Linux log management tools Logrotate (Linux)

- CentOS yum source configuration (Linux)

- Build a Linux development environment under STC89C52RC (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:      
 
- Install the open source database PostgreSQL 9.4 and phpMyAdmin on Ubuntu (Database)
- Storm how to ensure that at least once semantics (Programming)
- Linux performance optimization tools perf top (Linux)
- Learn about EditText little depth (Programming)
- How do I upgrade from Ubuntu 15.04 to Ubuntu 15.10 (Linux)
- C # asynchronous delegates (Programming)
- Why learn Java EE (Programming)
- Single Instance ASM under CRS-4124, CRS-4000 error handling (Database)
- Debian 7.6 install Nvidia graphics driver (Linux)
- CentOS 6.4 Telecom ADSL dial-up network configuration (Linux)
- Automatic Clear date directory shell script (Linux)
- Android project using the command to create and install the package (Programming)
- Linux system security reinforcement (Linux)
- The multiplexed signal driving IO (Programming)
- MySQL time field based partitioning scheme summary (Database)
- Firewall chapter of Linux server security configuration (Linux)
- Hadoop connection failed or stuck processing (Server)
- To install the mail client terminal Evolution 3.13.2 under Ubuntu 14.04 (Linux)
- Use OpenSSL to generate a certificate detailed process (Linux)
- RMAN parameters of ARCHIVELOG DELETION (Database)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.