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.