Xah Talk Show 2022-12-19 Difference Between List, Array, Vector, Why is Array Access Constant Time

different jargons for ordered sequence of things

Array, list, vector, tuple, all these jargons, essentially means almost the same thing, exactly what they mean depends on the language

• typically, they all mean, just order sequence of things.

• ordered sequence of things, is a natural math concept. you cannot escape it.

Implementation Detail, and Algorithmetic Properties

but they differ in some algorithmetic properties. the most fundamental are:

• how fast is it to access any nth item? does it take longer time to access items far from the first?
• can you add items to the list? and is it slow or fast? or can you delete items in the list?

why does these difference exist?

• because, it depends on the design of the machine (computer), and depends on the implementation of the algorithm, or, the programing language's implementation of its list/vector/array data structure.

what is a stack

• it's like a stack of books, you have 2 operations, push and pop.
• push is add an item to the top.
• pop is remove an item on the top.

algorithmetic property of lisp's list. (including common lisp, emacs lisp, scheme lisp, racket lisp, but not clojure lisp)

• it is slow, to access nth time. the further n is from 1, the longer time it takes.
• but, it is constant time, and fast, to add an item to the beginning of the list, or delete that item. but, if you want to delete or add at the nth item, it's proportionally slower.

critical concept: array (aka C or java array. fixed length array)

again, mathematically, it's an ordered sequence of things. but, this jargon “array”, by convention, has a specific algorithmic property. it is:

• fast, constant, access time, to any time.
• but, the array cannot grow nor shrink (i.e. cannot add or delete elements. if you do, you basically have to create a new array.)

Why is Array Access Constant Time, and why cannot we add or delete element in it in constant time?

• Why is Array Access Constant Time

critical concept: linked list

lisp's list, is called linked list, in computer science

• linked list, or in short, list, is a tail nested sequence of 2 items.

For example, suppose, we want a list, of items 1 2 3 4. in linked list, it looks like this:

[1, [2, [3, [4, nil]]]]

;; this shows, how lisp list is implemented as nested pairs
(equal
 (list 1 2 3 4)
 (cons 1 (cons 2 (cons 3 (cons 4 nil))))
)

python (list), ruby (array), JavaScript (array), their list (or called array), is a smart array (for lack of standard term)

their smart array/list, is such that, they internally create a new array with dobule the length when you want to add a item to the array, and hide that from you.

linked list, is the proper data structure for stack

implement linked list in python

# implement a linked list in python

# an ordered sequence of things
# with 2 operations: push and pop
# push is add an item in front
# pop is delete an item in front


def createLL(xlist):
    """create a linked list"""
    ll = ()
    for xx in xlist:
        ll = (xx, ll)
    return ll

def pushLL(xll, x):
    """add x to the front of linked list xll"""
    return (x, xll)

# def popLL(xll):
#     """delete the first item of linked list xll"""
#     xfirst = xll[0]
#     xll = xll[1]
#     return xfirst


def popLL(xll):
    """delete the first item of linked list xll"""
    return xll.pop()

x1 = createLL([1, 2])
print("x1 is", x1)
# print( type(x1) )

x2 = pushLL(x1, 3)
print("x1 is", x1)
print("x2 is", x2)

popLL(x2)
popLL(x2)
popLL(x2)
print("x1 is", x1)
print("x2 is", x2)

def pushPythonList(xlist, x):
    """add x to the end of python list xlist"""
    xlist.append(x)
    return xlist

def popPythonList(xlist):
    """delete the last item and return it, of python list xlist"""
    return xlist.pop()

# y1 = [1,2]
# print(y1)
# print( type(y1) )

# y2 = pushPythonList(y1, 3)
# print( y2)

# y3 = popPythonList(y2)
# print( y3)

# print( y2)

# implement a linked list in python

# an ordered sequence of things
# with 2 operations: push and pop
# push is add an item in front
# pop is delete an item in front


def createLL(xlist):
    """create a linked list"""
    ll = []
    for xx in xlist:
        ll = [xx, ll]
    return ll

def pushLL(xll, xnew):
    """add x to the front of linked list xll"""
    first = xll[0]
    rest = xll[1]
    xll[0] = xnew
    xll[1] = list(xll)
    return xll

# def popLL(xll):
#     """delete the first item of linked list xll"""
#     xfirst = xll[0]
#     xll = xll[1]
#     return xfirst


def popLL(xll):
    """delete the first item of linked list xll"""
    return xll.pop()

x1 = createLL([1, 2, 3])
print("x1 is", x1)
# print( type(x1) )

x2 = pushLL(x1, 4)
print("x1 is", x1)
print("x2 is", x2)

# popLL(x2)
# popLL(x2)
# popLL(x2)
# print("x1 is", x1)
# print("x2 is", x2)


def pushPythonList(xlist, x):
    """add x to the end of python list xlist"""
    xlist.append(x)
    return xlist

def popPythonList(xlist):
    """delete the last item and return it, of python list xlist"""
    return xlist.pop()

# y1 = [1,2]
# print(y1)
# print( type(y1) )

# y2 = pushPythonList(y1, 3)
# print( y2)

# y3 = popPythonList(y2)
# print( y3)

# print( y2)

# conclusion. efficient stack cannot be implement in python code, unles going to C.
# there is
# collections.deque
# let's see if its source code is in python or C
# github python collections.deque

correct implementation:

• Python: Implementing Efficient Stack