Linked Lists Implementation

Posted on | In , |

Advantage

  • Linked Lists are dynamic data structures, arrays are not
  • It can allocate the needed memory in runtime
  • Very efficient if we want to manipulate the first elements
  • Can store items with different sizes; an array assumes every element to be exactly the same
  • It is easier for a linked list to grow organically. An array’s size usually need to be known ahead of time or re-created when it needs to grow

Disadvantages

  • Waste memory because of the references
  • Nodes in a linked list must be read in order from the beginning as linked lists have sequential access (array items can be reached via indexes in O(1) time)
  • Solution: doubly linked lists -> easier to read, but memory is wasted in allocating space for a back pointer

Pros & Cons of an array

  • Pros
    • We can use random access by indexes, O(1)
    • Very fast implementation and use
    • Very fast data structure
    • A good choice when we want to add items over and over again and we want to get items with given indexes
  • Cons
    • Usually, we have to know the size of the array at compile time
    • If it is full we have to create a bigger array and have to copy values one by one.
    • It is not able to store items with different types (Not the case in Python)

Linked Lists vs Arrays

Linked Lists Arrays
search O(n) O(1) via index
insert at the start O(1) O(N)
insert at the end O(N) O(1)
Waste Space O(N) 0

Implementation

Linked List implementation with Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class Node(object):

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


class LinkedList(object):

    def __init__(self):
        self.head = None
        self.size = 0

    # O(1)
    def insertStart(self, data):

        self.size = self.size + 1
        newNode = Node(data)

        if not self.head:
            self.head = newNode
        else:
            newNode.nextNode = self.head
            self.head = newNode

    def remove(self, data):

        if self.head is None:
            return

        self.size = self.size - 1

        currentNode = self.head
        previousNode = None

        while currentNode.data != data:
            previousNode = currentNode
            currentNode = currentNode.nextNode

        if previousNode is None:
            self.head = currentNode.nextNode
        else:
            previousNode = currentNode.nextNode

    # O(1)
    def size1(self):

        return self.size

    # O(N) not good !!!!!
    def seize2(self):

        actualNode = self.head
        size = 0

        while actualNode is not None:
            size += 1
            actualNode = actualNode.nextNode

        return size

    # O(N)
    def insertEnd(self, data):

        self.size = self.size + 1
        newNode = Node(data)
        actualNode = self.head

        while actualNode.nextNode is not None:
            actualNode = actualNode.nextNode

        actualNode.nextNode = newNode

    def traverseList(self):

        actualNode = self.head

        while actualNode is not None:
            print('%d ' % actualNode.data)
            actualNode = actualNode.nextNode

# test
linkedList = LinkedList()

linkedList.insertStart(12)
linkedList.insertStart(122)
linkedList.insertStart(3)
linkedList.insertEnd(5)

linkedList.traverseList()

linkedList.remove(3)
linkedList.remove(5)
linkedList.remove(122)

print(linkedList.size1())

Other Note

abstract data types data structures
Stack array, linked list
Queue array, linked list
Priority queue heap
Dictionary / hashmap array
0%