Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Java implementation linear table - represents the order of representation and chain     - Linux System Tutorial: How to browse the Linux command line, weather forecast (Linux)

- PXE + Kickstart automatically install CentOS 6.5 (Linux)

- To access an Oracle database using Instant Client (Database)

- C # DateTime structure common method (Programming)

- To install Spotify in Ubuntu / Mint (Linux)

- CentOS source installation GitLab Chinese Version (Server)

- awk pattern matching (Programming)

- Linux kernel TCP / IP parameters analysis and tuning (Linux)

- On event processing browser compatibility notes (Programming)

- To share Internet access through NAT mode under Virtual Linux VMware Workstation (Linux)

- Jetty JNDI Development combat (Linux)

- Linux environment variable configuration (Linux)

- Windows Ubuntu dual system a key Ghost, grub rescue prompt solution (Linux)

- Android Send HTTP POST requests (Programming)

- httpd-2.4 feature (Server)

- Some problems and countermeasures Linux system calls exist (Linux)

- How do you access Dropbox Linux command line (Linux)

- CentOS ClamAV antivirus package updates (Linux)

- Installation and management of Linux applications (Linux)

- GDB remote connections RX Probe online debug program (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:      
 
- The method of installing software under Ubuntu Linux (Linux)
- Ubuntu 14.04 Fixed update information is outdated error (Linux)
- How to make GRub instead of the default Ubuntu software center (Linux)
- RHEL7 unattended automatic installation DHCP + TFTP + SYSLINUX + TFTP + Kickstart (Linux)
- Merge sort Java implementation (Programming)
- Linux Log (Linux)
- DRBD switchover (Server)
- Oracle lag () and lpad () function (Database)
- pga_aggregate_target and _pga_max_size can not use absolute limit actual PGA (Database)
- Linux system package manager (rpm, yum, source packages installation) (Linux)
- Use this one-time password via SSH secure login Linux (Programming)
- Default permissions Linux file and directory permissions and hide - umask, chattr, lsattr, SUID, SGID, SBIT, file (Linux)
- Docker + OpenvSwitch build experimental environment VxLAN (Server)
- grep, egrep and regular expressions (Linux)
- Linux Basics Tutorial: create your own Vim IDE (Linux)
- Linux based serial programming (Programming)
- Python function arguments * args and ** kwargs usage (Programming)
- Ubuntu 15.04 / 14.04 install Ubuntu After Install 2.6 (Linux)
- Ubuntu ADSL dial-up Internet access (Linux)
- CentOS 6.6 x64 Oracle Database 11gR2 RAC automated installation scripts (Database)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.