1. Singly Linked List

Singly Linked List¶

Operations¶

1. Add element
   • head
   • tail
   • in between
2. Traverse list
3. Get size of list/count number of elements
4. Delete element
   • head
   • tail
   • in between
5. Search

References

1. https://teamtreehouse.com/library/introduction-to-data-structures/building-a-linked-list/singly-and-doubly-linked-lists-2

2. https://teamtreehouse.com/library/introduction-to-data-structures/building-a-linked-list/linked-lists-operations

In [1]:

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

    def __repr__(self):
        return "<Node data: %s>" % self.data

class Node: def __init__(self, data): self.data = data self.next = None def __repr__(self): return "" % self.data

In [2]:

class LinkedList:
    """
    Operations on linked lists
    """

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

    def __repr__(self):
        nodes = []
        current = self.head
        while current:
            if current == self.head:
                nodes.append("[Head: %s]" % current.data)
            elif current.next == None:
                nodes.append("[Tail: %s]" % current.data)
            else:
                nodes.append("[%s]" % current.data)
            current = current.next
        return "->".join(nodes)

    def __len__(self):
        return self.__count

    # this is to make a linked list object iterable
    # probably the best example where I understood the
    # use of iterator
    def __iter__(self):

        current = self.head

        while current != None:
            yield current
            current = current.next

    def is_empty(self):
        return self.head == None

    def add_head(self, data):
        node = Node(data)
        if self.head == None:
            self.head = node
        else:
            node.next = self.head
            self.head = node

        self.__count += 1

    # correct/better implementaion
    def add_tail_1(self, data):
        node = Node(data)

        if self.head == None:
            self.head = node
        else:
            current = self.head
            while current.next != None:
                current = current.next
            current.next = node
        self.__count += 1

    def add_tail_2(self, data):
        node = Node(data)

        if self.head == None:
            self.head = node
        else:
            current = self.head
            while current != None:
                # here also we are stopping just at the last element
                # so that current doesn't point to None
                if current.next == None:
                    break
                else:
                    current = current.next
            current.next = node
        self.__count += 1

    def traverse_list(self):
        current = self.head
        while current != None:
            print(current.data)
            current = current.next

    def traverse_list_incorrect(self):
        while current.next != None:
            print(current.data)
            current = current.next

    def search(self, key):
        current = self.head
        while current != None:
            if current.data == key:
                return current
            current = current.next

        return None

    def insert(self, data, index):

        if index > self.__count:
            raise IndexError("index out of range")

        if index == 0:
            print("inserting [{}] at head".format(data))
            self.add_head(data)
        elif index == self.__count:
            print("inserting [{}] at tail".format(data))
            self.add_tail_1(data)
        else:
            node = Node(data)
            pos = 0
            current = self.head
            while current != None:
                pos += 1
                if pos == index:
                    print(
                        "inserting at position: {}, data at current: {}".format(
                            pos, current.data
                        )
                    )
                    node.next = current.next
                    current.next = node
                current = current.next
        self.__count += 1

    def node_at_index(self, index):
        if index < 0 or index > self.__count:
            raise IndexError("requested index out of bounds")

        elif index == 0:
            print("requsted node at head")
            return self.head

        elif index > 0:
            current = self.head
            pos = 0

            while current != None:
                if pos == index:
                    print("postion/index: {}, data: {}".format(pos, current.data))
                    return current
                pos += 1
                current = current.next

    def remove_key(self, key):
        # we can also say if self.head == None
        if self.__count == 0:
            print("List is empty, nothing to remove")
            return

        current = self.head
        previous = self.head
        found = False
        while current != None:
            if current.data == key:
                found = True
                break
            previous = current
            current = current.next

        if found:
            print("current: ", current)
            print("previous: ", previous)
            print("Removing key/element/item: {}".format(current.data))

            if current == previous:
                self.head = current.next
                del current
                self.__count -= 1
                return

            previous.next = current.next
            del current
            self.__count -= 1

        else:
            print("key not found")

    def remove_key_index(self, index):
        if index < 0 or index >= self.__count:
            print("index out of bounds")
            return

        current = self.head
        previous = self.head
        pos = 0
        # this is one way in which we do all the operations within
        # the while loop
        # other method is to traverse the list, break out when the
        # index is found and then do the removal
        # former is inspired by treehouse code
        # latter came by intuition
        # in fact the function `remove_key` has been implemented
        # with the latter approach
        while current != None:
            if index == 0:
                self.head = current.next
                print("Removing key/element/item: {}".format(current.data))
                del current
                self.__count -= 1
                break
            elif index == pos:
                previous.next = current.next
                print("Removing key/element/item: {}".format(current.data))
                del current
                self.__count -= 1
                break
            pos += 1
            previous = current
            current = current.next

    def reverse_MISTAKE(self):
        if self.__count < 0 or self.head == None:
            print("list is empty")
            return

        current = self.head
        prev = self.head
        temp = self.head
        while temp.next != None:
            temp = temp.next
            print("temp.data: ", temp.data)
            current.next = prev

            prev = current
            print("prev.data", prev.data)
            print("prev.next.data", prev.next.data)
            print("prev.next.next.data", prev.next.next.data)
            current = temp
            print("current.data", current.data)

            print()
        #
        print("current.next.data", current.next.data)
        print(self.head)
        self.head.next = None
        self.head = temp

    def reverse(self):
        if self.__count < 0 or self.head == None:
            print("list is empty")
            return

        current = self.head
        prev = self.head
        temp = self.head
        while temp.next != None:
            temp = temp.next
            current.next = prev

            prev = current
            current = temp

        # MAJOR MISTAKE
        # When I exit the loop, I forgot to assign current's next to prev
        # and that's how the connection broke even though
        # all the previous elements are correctly connected.
        current.next = prev
        self.head.next = None
        self.head = temp

class LinkedList: """ Operations on linked lists """ def __init__(self): self.head = None self.__count = 0 def __repr__(self): nodes = [] current = self.head while current: if current == self.head: nodes.append("[Head: %s]" % current.data) elif current.next == None: nodes.append("[Tail: %s]" % current.data) else: nodes.append("[%s]" % current.data) current = current.next return "->".join(nodes) def __len__(self): return self.__count # this is to make a linked list object iterable # probably the best example where I understood the # use of iterator def __iter__(self): current = self.head while current != None: yield current current = current.next def is_empty(self): return self.head == None def add_head(self, data): node = Node(data) if self.head == None: self.head = node else: node.next = self.head self.head = node self.__count += 1 # correct/better implementaion def add_tail_1(self, data): node = Node(data) if self.head == None: self.head = node else: current = self.head while current.next != None: current = current.next current.next = node self.__count += 1 def add_tail_2(self, data): node = Node(data) if self.head == None: self.head = node else: current = self.head while current != None: # here also we are stopping just at the last element # so that current doesn't point to None if current.next == None: break else: current = current.next current.next = node self.__count += 1 def traverse_list(self): current = self.head while current != None: print(current.data) current = current.next def traverse_list_incorrect(self): while current.next != None: print(current.data) current = current.next def search(self, key): current = self.head while current != None: if current.data == key: return current current = current.next return None def insert(self, data, index): if index > self.__count: raise IndexError("index out of range") if index == 0: print("inserting [{}] at head".format(data)) self.add_head(data) elif index == self.__count: print("inserting [{}] at tail".format(data)) self.add_tail_1(data) else: node = Node(data) pos = 0 current = self.head while current != None: pos += 1 if pos == index: print( "inserting at position: {}, data at current: {}".format( pos, current.data ) ) node.next = current.next current.next = node current = current.next self.__count += 1 def node_at_index(self, index): if index < 0 or index > self.__count: raise IndexError("requested index out of bounds") elif index == 0: print("requsted node at head") return self.head elif index > 0: current = self.head pos = 0 while current != None: if pos == index: print("postion/index: {}, data: {}".format(pos, current.data)) return current pos += 1 current = current.next def remove_key(self, key): # we can also say if self.head == None if self.__count == 0: print("List is empty, nothing to remove") return current = self.head previous = self.head found = False while current != None: if current.data == key: found = True break previous = current current = current.next if found: print("current: ", current) print("previous: ", previous) print("Removing key/element/item: {}".format(current.data)) if current == previous: self.head = current.next del current self.__count -= 1 return previous.next = current.next del current self.__count -= 1 else: print("key not found") def remove_key_index(self, index): if index < 0 or index >= self.__count: print("index out of bounds") return current = self.head previous = self.head pos = 0 # this is one way in which we do all the operations within # the while loop # other method is to traverse the list, break out when the # index is found and then do the removal # former is inspired by treehouse code # latter came by intuition # in fact the function `remove_key` has been implemented # with the latter approach while current != None: if index == 0: self.head = current.next print("Removing key/element/item: {}".format(current.data)) del current self.__count -= 1 break elif index == pos: previous.next = current.next print("Removing key/element/item: {}".format(current.data)) del current self.__count -= 1 break pos += 1 previous = current current = current.next def reverse_MISTAKE(self): if self.__count < 0 or self.head == None: print("list is empty") return current = self.head prev = self.head temp = self.head while temp.next != None: temp = temp.next print("temp.data: ", temp.data) current.next = prev prev = current print("prev.data", prev.data) print("prev.next.data", prev.next.data) print("prev.next.next.data", prev.next.next.data) current = temp print("current.data", current.data) print() # print("current.next.data", current.next.data) print(self.head) self.head.next = None self.head = temp def reverse(self): if self.__count < 0 or self.head == None: print("list is empty") return current = self.head prev = self.head temp = self.head while temp.next != None: temp = temp.next current.next = prev prev = current current = temp # MAJOR MISTAKE # When I exit the loop, I forgot to assign current's next to prev # and that's how the connection broke even though # all the previous elements are correctly connected. current.next = prev self.head.next = None self.head = temp

create and display a single node¶

In [3]:

node = Node(10)

node = Node(10)

In [4]:

node

node

Out[4]:

<Node data: 10>

create a linked list¶

In [5]:

l1 = LinkedList()
for i in range(4, 10):
    l1.add_head(i)

l1 = LinkedList() for i in range(4, 10): l1.add_head(i)

traverse linked list¶

In [6]:

l1.traverse_list()

l1.traverse_list()

9
8
7
6
5
4

iterate through linked list¶

• implemented __iter__ method

In [7]:

for i in l1:
    print(i)

for i in l1: print(i)

<Node data: 9>
<Node data: 8>
<Node data: 7>
<Node data: 6>
<Node data: 5>
<Node data: 4>

get length of linked list¶

• implemented __len__ method

In [8]:

len(l1)

len(l1)

Out[8]:

6

display linked list¶

• implemented __repr__ method

In [9]:

l1

l1

Out[9]:

[Head: 9]->[8]->[7]->[6]->[5]->[Tail: 4]

search an element in linked list¶

In [10]:

l1.search(6)

l1.search(6)

Out[10]:

<Node data: 6>

insert an element in linked list¶

In [11]:

l1.insert(200, 0)

l1.insert(200, 0)

inserting [200] at head

In [12]:

l1

l1

Out[12]:

[Head: 200]->[9]->[8]->[7]->[6]->[5]->[Tail: 4]

In [13]:

l1.insert(101, 2)

l1.insert(101, 2)

inserting at position: 2, data at current: 9

In [14]:

l1

l1

Out[14]:

[Head: 200]->[9]->[101]->[8]->[7]->[6]->[5]->[Tail: 4]

In [15]:

l1.insert(22, 8)

l1.insert(22, 8)

inserting at position: 8, data at current: 4

In [16]:

l1

l1

Out[16]:

[Head: 200]->[9]->[101]->[8]->[7]->[6]->[5]->[4]->[Tail: 22]

get element at index in linked list¶

In [17]:

l1.node_at_index(2)

l1.node_at_index(2)

postion/index: 2, data: 101

Out[17]:

<Node data: 101>

remove an element in linked list¶

In [18]:

l1.remove_key(7)

l1.remove_key(7)

current:  <Node data: 7>
previous:  <Node data: 8>
Removing key/element/item: 7

In [19]:

l1

l1

Out[19]:

[Head: 200]->[9]->[101]->[8]->[6]->[5]->[4]->[Tail: 22]

In [20]:

l1.remove_key(4)

l1.remove_key(4)

current:  <Node data: 4>
previous:  <Node data: 5>
Removing key/element/item: 4

In [21]:

l1

l1

Out[21]:

[Head: 200]->[9]->[101]->[8]->[6]->[5]->[Tail: 22]

In [22]:

l1.remove_key(9)

l1.remove_key(9)

current:  <Node data: 9>
previous:  <Node data: 200>
Removing key/element/item: 9

In [23]:

l1

l1

Out[23]:

[Head: 200]->[101]->[8]->[6]->[5]->[Tail: 22]

In [24]:

l1.remove_key(4)

l1.remove_key(4)

key not found

In [25]:

l1.remove_key(6)

l1.remove_key(6)

current:  <Node data: 6>
previous:  <Node data: 8>
Removing key/element/item: 6

In [26]:

l1

l1

Out[26]:

[Head: 200]->[101]->[8]->[5]->[Tail: 22]

In [27]:

l1.remove_key(5)

l1.remove_key(5)

current:  <Node data: 5>
previous:  <Node data: 8>
Removing key/element/item: 5

In [28]:

l1

l1

Out[28]:

[Head: 200]->[101]->[8]->[Tail: 22]

In [29]:

l1.remove_key(0)

l1.remove_key(0)

key not found

In [30]:

l1.remove_key(8)

l1.remove_key(8)

current:  <Node data: 8>
previous:  <Node data: 101>
Removing key/element/item: 8

In [31]:

l1.remove_key(0)

l1.remove_key(0)

key not found

remove key at a given index in linked list¶

In [32]:

l1.remove_key_index(3)

l1.remove_key_index(3)

In [33]:

l1

l1

Out[33]:

[Head: 200]->[101]->[Tail: 22]

In [34]:

l1.remove_key_index(10)

l1.remove_key_index(10)

index out of bounds

In [35]:

l1

l1

Out[35]:

[Head: 200]->[101]->[Tail: 22]

In [36]:

l1.remove_key_index(4)

l1.remove_key_index(4)

index out of bounds

In [37]:

l1

l1

Out[37]:

[Head: 200]->[101]->[Tail: 22]

In [38]:

l1.remove_key_index(2)

l1.remove_key_index(2)

Removing key/element/item: 22

In [39]:

l1

l1

Out[39]:

[Head: 200]->[Tail: 101]

In [40]:

l1.remove_key_index(0)

l1.remove_key_index(0)

Removing key/element/item: 200

In [41]:

l1

l1

Out[41]:

[Head: 101]

In [42]:

l1.remove_key_index(2)

l1.remove_key_index(2)

index out of bounds

In [43]:

l1

l1

Out[43]:

[Head: 101]

In [44]:

len(l1)

len(l1)

Out[44]:

2

In [45]:

l1.remove_key_index(1)

l1.remove_key_index(1)

In [46]:

l1

l1

Out[46]:

[Head: 101]

In [47]:

len(l1)

len(l1)

Out[47]:

2

In [48]:

l1.remove_key_index(1)

l1.remove_key_index(1)

In [49]:

l1.remove_key_index(0)

l1.remove_key_index(0)

Removing key/element/item: 101

In [50]:

l1

l1

Out[50]:

In [51]:

l = LinkedList()

l = LinkedList()

In [52]:

for i in range(0, 6):
    l.add_head(i)

for i in range(0, 6): l.add_head(i)

In [53]:

l

l

Out[53]:

[Head: 5]->[4]->[3]->[2]->[1]->[Tail: 0]

In [54]:

l.reverse()

l.reverse()

In [55]:

l

l

Out[55]:

[Head: 0]->[1]->[2]->[3]->[4]->[Tail: 5]

In [ ]: