Is linked list always slower than python list?

Question

I'm working on Problem Solving with Algorithms and Data Structures and come across this question: Design and implement an experiment that will compare the performance of a Python list with a list implemented as a linked list.

Below is my linked list implementation.

class Node(object):

    def __init__(self, data):
        self.data = data
        self.next = None

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next

    def set_data(self, new_data):
        self.data = new_data

    def set_next(self, new_next):
        self.next = new_next


class UnOrderedList(object):
    def __init__(self):
        self.N = 0
        self.head = None

    def size(self):
        return self.N

    def is_empty(self):
        return self.N == 0

    def add(self, data):
        self.N += 1
        temp = Node(data)
        temp.set_next(self.head)
        self.head = temp

    def search(self, data):
        current = self.head
        found = False
        while current and not found:
            if current.get_data() == data:
                found = True
            current = current.get_next()
        return found

    def remove(self, item):
        current = self.head
        previous = None
        while current.get_data() != item:
            previous = current
            current = current.get_next()
        if not previous:
            self.head = current.get_next()
        else:
            previous.set_next(current.get_next())
        self.N -= 1

test remove method:

for i in range(1000, 100000001, 100000):
    list1 = list(range(i))
    list2 = UnOrderedList()
    for a in range(i):
        list2.add(a)

    a = random.randrange(0, i)

    start_time1 = time.time()
    list1.remove(a)
    end_time1 = time.time()

    start_time2 = time.time()
    list2.remove(a)
    end_time2 = time.time()

    print("List time: {0}. Linked List time: {1}".format(end_time1-start_time1, end_time2-start_time2))

For my test, I test linked list's methods with python list's similar methods and linked list always comes up short. So I read a bit on the internet and find that though python list is better in index/search, linked list is supposed to trump it in add or remove.

So my question again is, is linked list always slower than list or what I am doing wrong?

Answer 1

Other answers have skipped a very important detail, Linked list will outperform arrays in say remove() method only when the pointer to node to be deleted is provided as parameter, not the value of node.

Otherwise, you will have to search through list, which has same O(n) complexity as removing element from an indexed-based list.

But there is another slightly less important factor at play here. Python list is actually implemented in C. A pure Python program is unlikely to beat a C counterpart, specially when that is written and optimized by experts for many years.

Answer 2

Python lists are implemented from arrays. So you are comparing Linked Lists to Arrays.

In Linked list you can insert/delete elements easily , but it takes more time in Arrays to move the other elements once the element is inserted/deleted.

Please refer comparison between array and linkedlist for more details. Also this quora question explains the implementation of list in python.

Answer 3

Well your test doesn't test something where a linked list would have an advantage. Here's a test where it does:

>>> from timeit import timeit

>>> linked_list = UnOrderedList()
>>> timeit(lambda: linked_list.add(0), number=10**5)
0.08297442221169149

>>> python_list = []
>>> timeit(lambda: python_list.insert(0, 0), number=10**5)
1.5988611595369093

Or you could just use your own test but without setting a to a random value (i.e., keep it at i-1):

List time: 0.0. Linked List time: 0.0
List time: 0.00100016593933. Linked List time: 0.0
List time: 0.00200009346008. Linked List time: 0.0
List time: 0.00300002098083. Linked List time: 0.0
List time: 0.00300002098083. Linked List time: 0.0
List time: 0.00399994850159. Linked List time: 0.0
List time: 0.00499987602234. Linked List time: 0.0
List time: 0.00699996948242. Linked List time: 0.0
List time: 0.00699996948242. Linked List time: 0.0
List time: 0.00799989700317. Linked List time: 0.0
List time: 0.00999999046326. Linked List time: 0.0
List time: 0.00899982452393. Linked List time: 0.0
...

Answer 4

Python's lists are based on C arrays. Arrays have the advantage over linked lists during iteration and random access, while linked lists have the advantage in random insertions and deletions.

This goes into detail of the theoretical differences betweent the two.

Answer 5

Think it deserves a dedicated answer, in terms of removal by value.

First, fix your test

In your example, arrays are different. Your linked list is in reversed order (100, 99, ...), because list2.add(a) adds to the start.

Quick fix is to reverse Python range, when populating linked list: range(i-1,-1,-1). This way elements will be in the same order as Python list.

Test

Now, test removals from list end to start (i-1, i-2, ...). Array list is faster (Python list) most of the time, while linked list gets closer (and faster further) only within 1% length to the list start (a = round(i / 99)).

So even though Python list needs to shift all the items following the deleted item, it's still faster.

That's due to internal Python implementation optimizations. As well as memory optimizations that are possible due to array list nature - because elements are sequential in memory, you get all the benefits out of data locality.

So yes, removals around list start (very close to start) are faster. But then, if you need such removals, just build Python array in the reversed order at first, and then delete from end, instead. It will be faster (as you observed above).

P.S. There are probably Python libraries with better Linked List implementation, but still, most of the time array list is faster.