At what level of abstraction are data structured created?

I am learning about Linked List and Arrays in my data structures class. We are make them in Java. Are actual data structures designed in Java/C? Or are they made in lower level languages like assembly? The linked list we made in class just seems to simple, it makes me wonder how real data structures differ from what I am being taught.

Here is a code snippet from one of the files:

import java.util.*;

/**
 * A class that implements our simple List interface using a linked list.
 * The linked list includes a dummy head node that allows us to avoid
 * special cases for insertion and deletion at the front of the list.
 */
public class LLList implements List {
    // Inner class for a node.  We use an inner class so that the LLList
    // methods can access the instance variables of the nodes.
    private class Node {
        private Object item;
        private Node next;

        private Node(Object i, Node n) {
            item = i;
            next = n;
        }
    }

    private Node head;     // dummy head node
    private int length;    // # of items in the list

    /**
     * Constructs a LLList object for a list that is initially empty.
     */
    public LLList() {
        head = new Node(null, null);
        length = 0;
    }

    /*
     * getNode - private helper method that returns a reference to the
     * ith node in the linked list.  It assumes that the value of the
     * parameter is valid.
     *
     * If i == -1, it returns a reference to the dummy head node.
     */
    private Node getNode(int i) {
        Node trav = head;
        int travIndex = -1;
        while (travIndex < i) {
            travIndex++;
            trav = trav.next;
        }
        return trav;
    }

    /** getItem - returns the item at position i in the list */
    public Object getItem(int i) {
        if (i < 0 || i >= length)
            throw new IndexOutOfBoundsException();
        Node n = getNode(i);
        return n.item;
    }

    /**
     * addItem - adds the specified item at position i in the list,
     * shifting the items that are currently in positions i, i+1, i+2,
     * etc. to the right by one.  Always returns true, because the list
     * is never full.
     *
     * We don't need a special case for insertion at the front of the
     * list (i == 0), because getNode(0 - 1) will return the dummy
     * head node, and the rest of insertion can proceed as usual.
     */
    public boolean addItem(Object item, int i) {
        if (i < 0 || i > length)
            throw new IndexOutOfBoundsException();

        Node newNode = new Node(item, null);
        Node prevNode = getNode(i - 1);
        newNode.next = prevNode.next;
        prevNode.next = newNode;

        length++;
        return true;
    }

    /**
     * removeItem - removes the item at position i in the list,
     * shifting the items that are currently in positions i+1, i+2,
     * etc. to the left by one.  Returns a reference to the removed
     * object.
     *
     * Here again, we don't need a special case for i == 0 (see the
     * note accompanying addItem above).
     */
    public Object removeItem(int i) {
        if (i < 0 || i >= length)
            throw new IndexOutOfBoundsException();

        Node prevNode = getNode(i - 1);
        Object removed = prevNode.next.item;
        prevNode.next = prevNode.next.next;

        length--;
        return removed;
    }

    /** length - returns the number of items in the list */
    public int length() {
        return length;
    }

    /**
     * isFull - always returns false, because the linked list can
     * grow indefinitely and thus the list is never full.
     */
    public boolean isFull() {
        return false;
    }

    /**
     * toString - converts the list into a String of the form
     * {item0, item1, ...}
     */
    public String toString() {
        String str = "{";

        Node trav = head.next;    // skip over the dummy head node
        while (trav != null) {
            str = str + trav.item;
            if (trav.next != null)
                str = str + ", ";
            trav = trav.next;
        }

        str = str + "}";
        return str;
    }

    /**
     * iterator - returns an iterator for this list
     */
    public ListIterator iterator() {
        return new LLListIterator();
    }

    /*
     *** private inner class for an iterator over an LLList ***
     */
    private class LLListIterator implements ListIterator {
        private Node nextNode;          // the next node to visit
        private Node lastVisitedNode;   // the most recently visited node

        public LLListIterator() {
            nextNode = head.next;
            lastVisitedNode = null;
        }

        /**
         * hasNext - does the iterator have additional items to visit?
         */
        public boolean hasNext() {
            return (nextNode != null);
        }

        /**
         * next - returns a reference to the next Object in the iteration
         */
        public Object next() {
            if (nextNode == null)
                throw new NoSuchElementException();

            Object item = nextNode.item;
            lastVisitedNode = nextNode;
            nextNode = nextNode.next;

            return item;
        }
    }
}

The answer is both. Data Structures are implemented at all levels of abstraction as far as languages go. For a reasonably high level language like Java where memory allocation is automatically managed, you’d define the data structure in terms of Java classes and methods.

In C, you’d define structures (or arrays) and the functions that operate on them. Additionally, since C does not have automatic memory management, you’d need to also allocate the space for the data structures to exist and so forth. You’d also need to tell the compiler when to deallocate that memory so that you don’t run out of memory (this is one way of getting memory leaks).

Java and C both compile to lower level languages, JVM bytecode and assembly language respectively. These each have their own representations of data and operations but they are more directly aligned with how the computer that the program is run on functions (in Java’s case, it’s a virtual computer but the process is similar). Memory management and so forth are specified by the compiler according to conventions set out by the compiler writers but if you were to write the assembly/bytecode yourself, you could do so but you’d need to be very aware of all of the operations required to move data and operate on it as well as have a good mental model of how the various registers and assembly commands map to the structure you’ve got in mind.

As far as the real data structures in the wild, they are often much more sophisticated than linked lists and arrays. They often use these as components but there is a whole class of tree based structures and graphs that don’t necessarily use either one but can be implemented with either basic structure. Examples include heaps, tries, and R-trees.

As far as usage goes, however, it is much more common to pick a preexisting data structure from a library available to a language than to roll your own. The reasons for this are many and varied but the most common are performance, security, and reliability. Programming language designers tend to be very educated people with a great deal of knowledge as to what the best possible solutions for representing each data structure are and how to go about implementing that representation in a given language.

Python’s lists for instance, use Timsort rather than Quicksort or Merge Sort because in practice it’s a faster sort. Another good example is that of synchronized vs unsynchronized data structures in Java. Vectors are deprecated in favor of ArrayList. Vectors provide individually synchronized access to itself which is often problematic in a multithreaded environment (exactly why this is the case is best left for another day). There are other ways of implementing similar functionality but at less cost in terms of time and space so people tend to use those now.

So while rolling your own data structures is a fantastic thing to do for a learning exercise, it’s something that you generally avoid unless you have no other option since the provided structures in the libraries of your languages are generally more thoroughly tested and more brutally optimized than anything you could hope to build on your own. That being said, it’s good to know how all this stuff is supposed to work so you can properly analyze the problem at hand and pick the appropriate structures to help you solve it, even if you’re only using off the shelf components.

Linked lists and arrays are very simple, but they are also real data structures. They’re the simplest way to deal with a list of items, with linked lists simpler for lists whose size we don’t know ahead of time, and arrays simpler for lists whose size (or maximum size) we do know.

You don’t have to dip down into a different, lower-level language (like assembly) to make data structures.

The linked list we made in class just seems to simple

In programming, there is no such thing as too simple, unless it can’t actually do what we need it to do. Like Einstein said, “Everything should be made as simple as possible, but no simpler.”

Don’t think that just because a data structure being used by a program is simple that the program itself is simple — you can do some very complex things with very simple data structures.

Sometimes data structures are nested inside each other to make more complex data structures. For instance, you could have a linked list of arrays, or an array of linked lists.

I would say data structures exist at least one level of abstraction below the programming language level, if not everywhere. That’s because compilers and interpreters create data structures out of whatever source code you give them.

If you’re more interested in whether one of these hidden intermediate steps (compiler, interpreter, etc.) use data structures you would recognize, the answer is also likely yes. Clojure implements arrays as trees “under the hood” for example.

Filed under: softwareengineering - @ 22:17

Thẻ: data-structures, java

Thiết kế website giá rẻ

Danh mục

At what level of abstraction are data structured created?