Implement a Linked List

04213

Data Structures Implementation in Python (7 Part Series)

1 Implement a Hashmap with its various methods
2 Implement Stack using a List.
… 3 more parts…
3 Implement a Queue using a List.
4 Implement a Deque using a List
5 Implement a Linked List
6 Implement a Stack using a Linked List
7 Implement a Queue using a Linked List

Problem statement: Implement a Linked List with it’s functions like inserting an element at start of the linked list and inserting at the end of linked list, searching an element in the list and removing an element from the list.

What is a Linked List?
It’s a linear data structure, but the elements are not stored in next to each other or in a sequence, but rather they’re linked using pointers.

Test Cases:

  1. Insert at start

    • Insert a None.
    • Insert at start in an empty linked list.
    • Insert at start in a non-empty linked list.

  2. Insert at end.

    • Insert a None.
    • Insert at end in an empty linked list.
    • Insert at end in a non-empty linked list.

  3. Search

    • Search for element present in linked list.
    • Search for element in an empty linked list.
    • Search for element not present in linked list.
    • Search for None.

  4. Remove

    • Remove element from an empty linked list.
    • Remove element from a non-empty linked list.
    • Remove element not present in linked list.
    • Remove a None.

  5. Length

    • Print length of the linked list.

Algorithm:

  1. Insert to start
    • If data is None
      • return
    • Create a new node with data
    • Set the next of new node to head
    • Set the head to the new node
  2. Insert to end
    • If data is None
      • return
    • Create a new node with data
    • If linked list is empty,
      • set the head to the node
    • Else,
      • iterate through the end of list
      • Set the next of last node to new node.

  3. Search

    • Initialise a current pointer to head
    • Iterate through the linked list
      • If value is matched, return the value
      • Else, move onto the next node

  4. Remove

    • Initialise a current pointer, pointing to node next to head
    • Initialise a previous pointer, pointing to head
    • Iterate through the linked list,
      • If value is found,
        • Set the previous node, next pointer to current node next
      • Else, move onto the next node

  5. Length

    • Initialise a counter
    • Iterate through the entire linked list
    • For each node in the list,
      • increase the counter
    • Return the counter

Time Complexity:

  1. Insert to start
    • Time complexity: O(1)
    • Space complexity: O(1)
  2. Insert to end
    • Time complexity: O(n)
    • Space complexity: O(1)
  3. Search
    • Time complexity: O(n)
    • Space complexity: O(1)
  4. Remove
    • Time complexity: O(n)
    • Space complexity: O(1)
  5. Length
    • Time complexity: O(n)
    • Space complexity: O(1)

Code 

<span>class</span> <span>Node</span><span>(</span><span>object</span><span>):</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>,</span> <span>next</span><span>=</span><span>None</span><span>):</span>
        <span>self</span><span>.</span><span>data</span> <span>=</span> <span>data</span>
        <span>self</span><span>.</span><span>next</span> <span>=</span> <span>next</span>
<span>class</span> <span>LinkedList</span><span>(</span><span>object</span><span>):</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span> <span>head</span><span>=</span><span>None</span><span>):</span>
        <span>self</span><span>.</span><span>head</span> <span>=</span> <span>head</span>
    <span>def</span> <span>__len__</span><span>(</span><span>self</span><span>):</span>
        <span>current</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>counter</span> <span>=</span> <span>0</span>
        <span>while</span> <span>current</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>counter</span> <span>+=</span> <span>1</span>
            <span>current</span> <span>=</span> <span>current</span><span>.</span><span>next</span>
        <span>return</span> <span>counter</span>
    <span>def</span> <span>insertStart</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>):</span>
        <span>if</span> <span>data</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>None</span>
        <span>node</span> <span>=</span> <span>Node</span><span>(</span><span>data</span><span>,</span> <span>self</span><span>.</span><span>head</span><span>)</span>
        <span>self</span><span>.</span><span>head</span> <span>=</span> <span>node</span>
        <span>return</span> <span>node</span>
    <span>def</span> <span>insertEnd</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>):</span>
        <span>if</span> <span>data</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>None</span>
        <span>node</span> <span>=</span> <span>Node</span><span>(</span><span>data</span><span>)</span>
        <span>if</span> <span>self</span><span>.</span><span>head</span> <span>is</span> <span>None</span><span>:</span>
            <span>self</span><span>.</span><span>head</span> <span>=</span> <span>node</span>
            <span>return</span> <span>node</span>
        <span>curr_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>while</span> <span>curr_node</span><span>.</span><span>next</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>
        <span>curr_node</span><span>.</span><span>next</span> <span>=</span> <span>node</span>
        <span>return</span> <span>node</span>
    <span>def</span> <span>search</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>):</span>
        <span>if</span> <span>data</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>None</span>
        <span>curr_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>while</span> <span>curr_node</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>if</span> <span>curr_node</span><span>.</span><span>data</span> <span>==</span> <span>data</span><span>:</span>
                <span>return</span> <span>curr_node</span><span>.</span><span>data</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>
        <span>return</span> <span>None</span>
    <span>def</span> <span>remove</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>):</span>
        <span>if</span> <span>data</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>None</span>
        <span>if</span> <span>self</span><span>.</span><span>head</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span>
        <span>if</span> <span>self</span><span>.</span><span>head</span><span>.</span><span>data</span> <span>==</span> <span>data</span><span>:</span>
            <span>self</span><span>.</span><span>head</span> <span>=</span> <span>self</span><span>.</span><span>head</span><span>.</span><span>next</span>
            <span>return</span>
        <span>prev_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>curr_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span><span>.</span><span>next</span>
        <span>while</span> <span>curr_node</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>if</span> <span>curr_node</span><span>.</span><span>data</span> <span>==</span> <span>data</span><span>:</span>
                <span>prev_node</span><span>.</span><span>next</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>
                <span>return</span>
            <span>prev_node</span> <span>=</span> <span>curr_node</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>
    <span>def</span> <span>remove2</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>):</span>
        <span>if</span> <span>data</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>None</span>
        <span>if</span> <span>self</span><span>.</span><span>head</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>None</span>
        <span>curr_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>if</span> <span>curr_node</span><span>.</span><span>data</span> <span>==</span> <span>data</span><span>:</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>
            <span>return</span>
        <span>while</span> <span>curr_node</span><span>.</span><span>next</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>if</span> <span>curr_node</span><span>.</span><span>next</span><span>.</span><span>data</span> <span>==</span> <span>data</span><span>:</span>
                <span>curr_node</span><span>.</span><span>next</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span><span>.</span><span>next</span>
                <span>return</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>
    <span>def</span> <span>printList</span><span>(</span><span>self</span><span>):</span>
        <span>curr_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>while</span> <span>curr_node</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>print</span><span>(</span><span>curr_node</span><span>.</span><span>data</span><span>)</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>
    <span>def</span> <span>getData</span><span>(</span><span>self</span><span>):</span>
        <span>data</span> <span>=</span> <span>[]</span>
        <span>curr_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>while</span> <span>curr_node</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>data</span><span>.</span><span>append</span><span>(</span><span>curr_node</span><span>.</span><span>data</span><span>)</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>
        <span>return</span> <span>data</span>
<span>class</span> <span>Node</span><span>(</span><span>object</span><span>):</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>,</span> <span>next</span><span>=</span><span>None</span><span>):</span>
        <span>self</span><span>.</span><span>data</span> <span>=</span> <span>data</span>
        <span>self</span><span>.</span><span>next</span> <span>=</span> <span>next</span>


<span>class</span> <span>LinkedList</span><span>(</span><span>object</span><span>):</span>
    <span>def</span> <span>__init__</span><span>(</span><span>self</span><span>,</span> <span>head</span><span>=</span><span>None</span><span>):</span>
        <span>self</span><span>.</span><span>head</span> <span>=</span> <span>head</span>

    <span>def</span> <span>__len__</span><span>(</span><span>self</span><span>):</span>
        <span>current</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>counter</span> <span>=</span> <span>0</span>
        <span>while</span> <span>current</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>counter</span> <span>+=</span> <span>1</span>
            <span>current</span> <span>=</span> <span>current</span><span>.</span><span>next</span>
        <span>return</span> <span>counter</span>

    <span>def</span> <span>insertStart</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>):</span>
        <span>if</span> <span>data</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>None</span>
        <span>node</span> <span>=</span> <span>Node</span><span>(</span><span>data</span><span>,</span> <span>self</span><span>.</span><span>head</span><span>)</span>
        <span>self</span><span>.</span><span>head</span> <span>=</span> <span>node</span>
        <span>return</span> <span>node</span>

    <span>def</span> <span>insertEnd</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>):</span>
        <span>if</span> <span>data</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>None</span>
        <span>node</span> <span>=</span> <span>Node</span><span>(</span><span>data</span><span>)</span>
        <span>if</span> <span>self</span><span>.</span><span>head</span> <span>is</span> <span>None</span><span>:</span>
            <span>self</span><span>.</span><span>head</span> <span>=</span> <span>node</span>
            <span>return</span> <span>node</span>
        <span>curr_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>while</span> <span>curr_node</span><span>.</span><span>next</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>
        <span>curr_node</span><span>.</span><span>next</span> <span>=</span> <span>node</span>
        <span>return</span> <span>node</span>

    <span>def</span> <span>search</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>):</span>
        <span>if</span> <span>data</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>None</span>
        <span>curr_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>while</span> <span>curr_node</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>if</span> <span>curr_node</span><span>.</span><span>data</span> <span>==</span> <span>data</span><span>:</span>
                <span>return</span> <span>curr_node</span><span>.</span><span>data</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>
        <span>return</span> <span>None</span>

    <span>def</span> <span>remove</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>):</span>
        <span>if</span> <span>data</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>None</span>
        <span>if</span> <span>self</span><span>.</span><span>head</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span>
        <span>if</span> <span>self</span><span>.</span><span>head</span><span>.</span><span>data</span> <span>==</span> <span>data</span><span>:</span>
            <span>self</span><span>.</span><span>head</span> <span>=</span> <span>self</span><span>.</span><span>head</span><span>.</span><span>next</span>
            <span>return</span>
        <span>prev_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>curr_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span><span>.</span><span>next</span>
        <span>while</span> <span>curr_node</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>if</span> <span>curr_node</span><span>.</span><span>data</span> <span>==</span> <span>data</span><span>:</span>
                <span>prev_node</span><span>.</span><span>next</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>
                <span>return</span>
            <span>prev_node</span> <span>=</span> <span>curr_node</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>

    <span>def</span> <span>remove2</span><span>(</span><span>self</span><span>,</span> <span>data</span><span>):</span>
        <span>if</span> <span>data</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>None</span>
        <span>if</span> <span>self</span><span>.</span><span>head</span> <span>is</span> <span>None</span><span>:</span>
            <span>return</span> <span>None</span>
        <span>curr_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>if</span> <span>curr_node</span><span>.</span><span>data</span> <span>==</span> <span>data</span><span>:</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>
            <span>return</span>
        <span>while</span> <span>curr_node</span><span>.</span><span>next</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>if</span> <span>curr_node</span><span>.</span><span>next</span><span>.</span><span>data</span> <span>==</span> <span>data</span><span>:</span>
                <span>curr_node</span><span>.</span><span>next</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span><span>.</span><span>next</span>
                <span>return</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>

    <span>def</span> <span>printList</span><span>(</span><span>self</span><span>):</span>
        <span>curr_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>while</span> <span>curr_node</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>print</span><span>(</span><span>curr_node</span><span>.</span><span>data</span><span>)</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>

    <span>def</span> <span>getData</span><span>(</span><span>self</span><span>):</span>
        <span>data</span> <span>=</span> <span>[]</span>
        <span>curr_node</span> <span>=</span> <span>self</span><span>.</span><span>head</span>
        <span>while</span> <span>curr_node</span> <span>is</span> <span>not</span> <span>None</span><span>:</span>
            <span>data</span><span>.</span><span>append</span><span>(</span><span>curr_node</span><span>.</span><span>data</span><span>)</span>
            <span>curr_node</span> <span>=</span> <span>curr_node</span><span>.</span><span>next</span>
        <span>return</span> <span>data</span>
class Node(object):
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

    def __len__(self):
        current = self.head
        counter = 0
        while current is not None:
            counter += 1
            current = current.next
        return counter

    def insertStart(self, data):
        if data is None:
            return None
        node = Node(data, self.head)
        self.head = node
        return node

    def insertEnd(self, data):
        if data is None:
            return None
        node = Node(data)
        if self.head is None:
            self.head = node
            return node
        curr_node = self.head
        while curr_node.next is not None:
            curr_node = curr_node.next
        curr_node.next = node
        return node

    def search(self, data):
        if data is None:
            return None
        curr_node = self.head
        while curr_node is not None:
            if curr_node.data == data:
                return curr_node.data
            curr_node = curr_node.next
        return None

    def remove(self, data):
        if data is None:
            return None
        if self.head is None:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        prev_node = self.head
        curr_node = self.head.next
        while curr_node is not None:
            if curr_node.data == data:
                prev_node.next = curr_node.next
                return
            prev_node = curr_node
            curr_node = curr_node.next

    def remove2(self, data):
        if data is None:
            return None
        if self.head is None:
            return None
        curr_node = self.head
        if curr_node.data == data:
            curr_node = curr_node.next
            return
        while curr_node.next is not None:
            if curr_node.next.data == data:
                curr_node.next = curr_node.next.next
                return
            curr_node = curr_node.next

    def printList(self):
        curr_node = self.head
        while curr_node is not None:
            print(curr_node.data)
            curr_node = curr_node.next

    def getData(self):
        data = []
        curr_node = self.head
        while curr_node is not None:
            data.append(curr_node.data)
            curr_node = curr_node.next
        return data

Enter fullscreen mode Exit fullscreen mode

Unit Test 

<span>import</span> <span>unittest</span>
<span>from</span> <span>linkedList</span> <span>import</span> <span>LinkedList</span><span>,</span> <span>Node</span>
<span>class</span> <span>TestLinkedList</span><span>(</span><span>unittest</span><span>.</span><span>TestCase</span><span>):</span>
    <span>def</span> <span>testInsertStart</span><span>(</span><span>self</span><span>):</span>
        <span>print</span><span>(</span><span>'Test: insertStart on an empty linked list'</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>None</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>1</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>1</span><span>])</span>
        <span>print</span><span>(</span><span>'Test: insertStart on a None'</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>None</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>1</span><span>])</span>
        <span>print</span><span>(</span><span>'Test: insertStart on a non-empty linked list'</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>11</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>'letters'</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>'letters'</span><span>,</span> <span>11</span><span>,</span> <span>1</span><span>])</span>
        <span>print</span><span>(</span><span>'Success: testInsertStart'</span><span>)</span>
    <span>def</span> <span>testInsertEnd</span><span>(</span><span>self</span><span>):</span>
        <span>print</span><span>(</span><span>'Test: insertLast on an empty linked list'</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>None</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>2</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>2</span><span>])</span>
        <span>print</span><span>(</span><span>'Test: insertEnd a None'</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>None</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>2</span><span>])</span>
        <span>print</span><span>(</span><span>'Test: insertEnd on a non-empty linked list'</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>'4'</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>6</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>2</span><span>,</span> <span>'4'</span><span>,</span> <span>6</span><span>])</span>
        <span>print</span><span>(</span><span>'Success: insertEnd'</span><span>)</span>
    <span>def</span> <span>testSearch</span><span>(</span><span>self</span><span>):</span>
        <span>print</span><span>(</span><span>'Test: Search on an empty linked list'</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>None</span><span>)</span>
        <span>element</span> <span>=</span> <span>linkedList</span><span>.</span><span>search</span><span>(</span><span>1</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>element</span><span>,</span> <span>None</span><span>)</span>
        <span>print</span><span>(</span><span>'Test: Search on a None'</span><span>)</span>
        <span>linkedList1</span> <span>=</span> <span>LinkedList</span><span>(</span><span>10</span><span>)</span>
        <span>element</span> <span>=</span> <span>linkedList1</span><span>.</span><span>search</span><span>(</span><span>None</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>element</span><span>,</span> <span>None</span><span>)</span>
        <span>print</span><span>(</span><span>'Test: Search on a non-empty linked list'</span><span>)</span>
        <span>head</span> <span>=</span> <span>Node</span><span>(</span><span>10</span><span>)</span>
        <span>linkedList2</span> <span>=</span> <span>LinkedList</span><span>(</span><span>head</span><span>)</span>
        <span>linkedList2</span><span>.</span><span>insertStart</span><span>(</span><span>9</span><span>)</span>
        <span>linkedList2</span><span>.</span><span>insertStart</span><span>(</span><span>8</span><span>)</span>
        <span>linkedList2</span><span>.</span><span>insertStart</span><span>(</span><span>7</span><span>)</span>
        <span>linkedList2</span><span>.</span><span>insertEnd</span><span>(</span><span>11</span><span>)</span>
        <span>element</span> <span>=</span> <span>linkedList2</span><span>.</span><span>search</span><span>(</span><span>11</span><span>)</span>
        <span>element2</span> <span>=</span> <span>linkedList2</span><span>.</span><span>search</span><span>(</span><span>'aaa'</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>element</span><span>,</span> <span>11</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>element2</span><span>,</span> <span>None</span><span>)</span>
        <span>print</span><span>(</span><span>'Success: testSearch'</span><span>)</span>
    <span>def</span> <span>testRemove</span><span>(</span><span>self</span><span>):</span>
        <span>print</span><span>(</span><span>'Test: remove element from an empty linked list'</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>None</span><span>)</span>
        <span>linkedList</span><span>.</span><span>remove</span><span>(</span><span>2</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[])</span>
        <span>print</span><span>(</span><span>'Test: remove a None'</span><span>)</span>
        <span>head</span> <span>=</span> <span>Node</span><span>(</span><span>1</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>head</span><span>)</span>
        <span>linkedList</span><span>.</span><span>remove</span><span>(</span><span>None</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>1</span><span>])</span>
        <span>print</span><span>(</span><span>'Test: remove element from a non-empty linked list'</span><span>)</span>
        <span>head</span> <span>=</span> <span>Node</span><span>(</span><span>1</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>head</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>2</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>3</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>0</span><span>)</span>
        <span>linkedList</span><span>.</span><span>remove</span><span>(</span><span>0</span><span>)</span>
        <span>linkedList</span><span>.</span><span>remove2</span><span>(</span><span>2</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>1</span><span>,</span> <span>3</span><span>])</span>
        <span>linkedList</span><span>.</span><span>remove</span><span>(</span><span>'abc'</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>1</span><span>,</span> <span>3</span><span>])</span>
        <span>print</span><span>(</span><span>'Success: testRemove'</span><span>)</span>
    <span>def</span> <span>testLen</span><span>(</span><span>self</span><span>):</span>
        <span>print</span><span>(</span><span>'Test length of thean empty linked list'</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>None</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>len</span><span>(</span><span>linkedList</span><span>),</span> <span>0</span><span>)</span>
        <span>print</span><span>(</span><span>'Test length of non empty linked list'</span><span>)</span>
        <span>head</span> <span>=</span> <span>Node</span><span>(</span><span>0</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>head</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>1</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>2</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>3</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>len</span><span>(</span><span>linkedList</span><span>),</span> <span>4</span><span>)</span>
        <span>print</span><span>(</span><span>'Success: testLen'</span><span>)</span>
<span>def</span> <span>main</span><span>():</span>
    <span>test</span> <span>=</span> <span>TestLinkedList</span><span>()</span>
    <span>test</span><span>.</span><span>testInsertStart</span><span>()</span>
    <span>test</span><span>.</span><span>testInsertEnd</span><span>()</span>
    <span>test</span><span>.</span><span>testSearch</span><span>()</span>
    <span>test</span><span>.</span><span>testRemove</span><span>()</span>
    <span>test</span><span>.</span><span>testLen</span><span>()</span>
<span>if</span> <span>__name__</span> <span>==</span> <span>"__main__"</span><span>:</span>
    <span>main</span><span>()</span>
<span>import</span> <span>unittest</span>
<span>from</span> <span>linkedList</span> <span>import</span> <span>LinkedList</span><span>,</span> <span>Node</span>


<span>class</span> <span>TestLinkedList</span><span>(</span><span>unittest</span><span>.</span><span>TestCase</span><span>):</span>

    <span>def</span> <span>testInsertStart</span><span>(</span><span>self</span><span>):</span>
        <span>print</span><span>(</span><span>'Test: insertStart on an empty linked list'</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>None</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>1</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>1</span><span>])</span>

        <span>print</span><span>(</span><span>'Test: insertStart on a None'</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>None</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>1</span><span>])</span>

        <span>print</span><span>(</span><span>'Test: insertStart on a non-empty linked list'</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>11</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>'letters'</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>'letters'</span><span>,</span> <span>11</span><span>,</span> <span>1</span><span>])</span>

        <span>print</span><span>(</span><span>'Success: testInsertStart'</span><span>)</span>

    <span>def</span> <span>testInsertEnd</span><span>(</span><span>self</span><span>):</span>
        <span>print</span><span>(</span><span>'Test: insertLast on an empty linked list'</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>None</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>2</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>2</span><span>])</span>

        <span>print</span><span>(</span><span>'Test: insertEnd a None'</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>None</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>2</span><span>])</span>

        <span>print</span><span>(</span><span>'Test: insertEnd on a non-empty linked list'</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>'4'</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>6</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>2</span><span>,</span> <span>'4'</span><span>,</span> <span>6</span><span>])</span>

        <span>print</span><span>(</span><span>'Success: insertEnd'</span><span>)</span>

    <span>def</span> <span>testSearch</span><span>(</span><span>self</span><span>):</span>
        <span>print</span><span>(</span><span>'Test: Search on an empty linked list'</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>None</span><span>)</span>
        <span>element</span> <span>=</span> <span>linkedList</span><span>.</span><span>search</span><span>(</span><span>1</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>element</span><span>,</span> <span>None</span><span>)</span>

        <span>print</span><span>(</span><span>'Test: Search on a None'</span><span>)</span>
        <span>linkedList1</span> <span>=</span> <span>LinkedList</span><span>(</span><span>10</span><span>)</span>
        <span>element</span> <span>=</span> <span>linkedList1</span><span>.</span><span>search</span><span>(</span><span>None</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>element</span><span>,</span> <span>None</span><span>)</span>

        <span>print</span><span>(</span><span>'Test: Search on a non-empty linked list'</span><span>)</span>
        <span>head</span> <span>=</span> <span>Node</span><span>(</span><span>10</span><span>)</span>
        <span>linkedList2</span> <span>=</span> <span>LinkedList</span><span>(</span><span>head</span><span>)</span>
        <span>linkedList2</span><span>.</span><span>insertStart</span><span>(</span><span>9</span><span>)</span>
        <span>linkedList2</span><span>.</span><span>insertStart</span><span>(</span><span>8</span><span>)</span>
        <span>linkedList2</span><span>.</span><span>insertStart</span><span>(</span><span>7</span><span>)</span>
        <span>linkedList2</span><span>.</span><span>insertEnd</span><span>(</span><span>11</span><span>)</span>
        <span>element</span> <span>=</span> <span>linkedList2</span><span>.</span><span>search</span><span>(</span><span>11</span><span>)</span>
        <span>element2</span> <span>=</span> <span>linkedList2</span><span>.</span><span>search</span><span>(</span><span>'aaa'</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>element</span><span>,</span> <span>11</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>element2</span><span>,</span> <span>None</span><span>)</span>
        <span>print</span><span>(</span><span>'Success: testSearch'</span><span>)</span>

    <span>def</span> <span>testRemove</span><span>(</span><span>self</span><span>):</span>
        <span>print</span><span>(</span><span>'Test: remove element from an empty linked list'</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>None</span><span>)</span>
        <span>linkedList</span><span>.</span><span>remove</span><span>(</span><span>2</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[])</span>

        <span>print</span><span>(</span><span>'Test: remove a None'</span><span>)</span>
        <span>head</span> <span>=</span> <span>Node</span><span>(</span><span>1</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>head</span><span>)</span>
        <span>linkedList</span><span>.</span><span>remove</span><span>(</span><span>None</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>1</span><span>])</span>

        <span>print</span><span>(</span><span>'Test: remove element from a non-empty linked list'</span><span>)</span>
        <span>head</span> <span>=</span> <span>Node</span><span>(</span><span>1</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>head</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>2</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>3</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>0</span><span>)</span>
        <span>linkedList</span><span>.</span><span>remove</span><span>(</span><span>0</span><span>)</span>
        <span>linkedList</span><span>.</span><span>remove2</span><span>(</span><span>2</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>1</span><span>,</span> <span>3</span><span>])</span>
        <span>linkedList</span><span>.</span><span>remove</span><span>(</span><span>'abc'</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>linkedList</span><span>.</span><span>getData</span><span>(),</span> <span>[</span><span>1</span><span>,</span> <span>3</span><span>])</span>

        <span>print</span><span>(</span><span>'Success: testRemove'</span><span>)</span>

    <span>def</span> <span>testLen</span><span>(</span><span>self</span><span>):</span>
        <span>print</span><span>(</span><span>'Test length of thean empty linked list'</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>None</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>len</span><span>(</span><span>linkedList</span><span>),</span> <span>0</span><span>)</span>

        <span>print</span><span>(</span><span>'Test length of non empty linked list'</span><span>)</span>
        <span>head</span> <span>=</span> <span>Node</span><span>(</span><span>0</span><span>)</span>
        <span>linkedList</span> <span>=</span> <span>LinkedList</span><span>(</span><span>head</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>1</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertStart</span><span>(</span><span>2</span><span>)</span>
        <span>linkedList</span><span>.</span><span>insertEnd</span><span>(</span><span>3</span><span>)</span>
        <span>self</span><span>.</span><span>assertEqual</span><span>(</span><span>len</span><span>(</span><span>linkedList</span><span>),</span> <span>4</span><span>)</span>

        <span>print</span><span>(</span><span>'Success: testLen'</span><span>)</span>


<span>def</span> <span>main</span><span>():</span>
    <span>test</span> <span>=</span> <span>TestLinkedList</span><span>()</span>
    <span>test</span><span>.</span><span>testInsertStart</span><span>()</span>
    <span>test</span><span>.</span><span>testInsertEnd</span><span>()</span>
    <span>test</span><span>.</span><span>testSearch</span><span>()</span>
    <span>test</span><span>.</span><span>testRemove</span><span>()</span>
    <span>test</span><span>.</span><span>testLen</span><span>()</span>


<span>if</span> <span>__name__</span> <span>==</span> <span>"__main__"</span><span>:</span>
    <span>main</span><span>()</span>
import unittest
from linkedList import LinkedList, Node


class TestLinkedList(unittest.TestCase):

    def testInsertStart(self):
        print('Test: insertStart on an empty linked list')
        linkedList = LinkedList(None)
        linkedList.insertStart(1)
        self.assertEqual(linkedList.getData(), [1])

        print('Test: insertStart on a None')
        linkedList.insertStart(None)
        self.assertEqual(linkedList.getData(), [1])

        print('Test: insertStart on a non-empty linked list')
        linkedList.insertStart(11)
        linkedList.insertStart('letters')
        self.assertEqual(linkedList.getData(), ['letters', 11, 1])

        print('Success: testInsertStart')

    def testInsertEnd(self):
        print('Test: insertLast on an empty linked list')
        linkedList = LinkedList(None)
        linkedList.insertEnd(2)
        self.assertEqual(linkedList.getData(), [2])

        print('Test: insertEnd a None')
        linkedList.insertEnd(None)
        self.assertEqual(linkedList.getData(), [2])

        print('Test: insertEnd on a non-empty linked list')
        linkedList.insertEnd('4')
        linkedList.insertEnd(6)
        self.assertEqual(linkedList.getData(), [2, '4', 6])

        print('Success: insertEnd')

    def testSearch(self):
        print('Test: Search on an empty linked list')
        linkedList = LinkedList(None)
        element = linkedList.search(1)
        self.assertEqual(element, None)

        print('Test: Search on a None')
        linkedList1 = LinkedList(10)
        element = linkedList1.search(None)
        self.assertEqual(element, None)

        print('Test: Search on a non-empty linked list')
        head = Node(10)
        linkedList2 = LinkedList(head)
        linkedList2.insertStart(9)
        linkedList2.insertStart(8)
        linkedList2.insertStart(7)
        linkedList2.insertEnd(11)
        element = linkedList2.search(11)
        element2 = linkedList2.search('aaa')
        self.assertEqual(element, 11)
        self.assertEqual(element2, None)
        print('Success: testSearch')

    def testRemove(self):
        print('Test: remove element from an empty linked list')
        linkedList = LinkedList(None)
        linkedList.remove(2)
        self.assertEqual(linkedList.getData(), [])

        print('Test: remove a None')
        head = Node(1)
        linkedList = LinkedList(head)
        linkedList.remove(None)
        self.assertEqual(linkedList.getData(), [1])

        print('Test: remove element from a non-empty linked list')
        head = Node(1)
        linkedList = LinkedList(head)
        linkedList.insertEnd(2)
        linkedList.insertEnd(3)
        linkedList.insertStart(0)
        linkedList.remove(0)
        linkedList.remove2(2)
        self.assertEqual(linkedList.getData(), [1, 3])
        linkedList.remove('abc')
        self.assertEqual(linkedList.getData(), [1, 3])

        print('Success: testRemove')

    def testLen(self):
        print('Test length of thean empty linked list')
        linkedList = LinkedList(None)
        self.assertEqual(len(linkedList), 0)

        print('Test length of non empty linked list')
        head = Node(0)
        linkedList = LinkedList(head)
        linkedList.insertStart(1)
        linkedList.insertStart(2)
        linkedList.insertEnd(3)
        self.assertEqual(len(linkedList), 4)

        print('Success: testLen')


def main():
    test = TestLinkedList()
    test.testInsertStart()
    test.testInsertEnd()
    test.testSearch()
    test.testRemove()
    test.testLen()


if __name__ == "__main__":
    main()

Enter fullscreen mode Exit fullscreen mode

Github solution repo

Happy coding ⭐

Data Structures Implementation in Python (7 Part Series)

1 Implement a Hashmap with its various methods
2 Implement Stack using a List.
… 3 more parts…
3 Implement a Queue using a List.
4 Implement a Deque using a List
5 Implement a Linked List
6 Implement a Stack using a Linked List
7 Implement a Queue using a Linked List

原文链接：Implement a Linked List

展开阅读全文
© 版权声明
文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END
Python（EN）
# python# tutorial# computerscience
喜欢就支持一下吧
点赞13 分享
Time always save the best for last.
时间总把最好的人留到最后
评论 抢沙发

请登录后发表评论

    暂无评论内容

kity的头像-拾光赋
今日剩余 82.5%
本周剩余 54.6%
本月剩余 46.1%
本年剩余 70.9%
最近评论
杀人蜂的头像-拾光赋

杀人蜂3天前0

我很好奇这个网站能提供什么
Vito的头像-拾光赋

Vito6个月前2

你就是我心中的那首忐忑，总是让我惊心动魄
Jason.Meng的头像-拾光赋钻石会员

Jason.Meng徽章-人气大使-拾光赋6个月前2

总是会在人生的不同阶段反复爱上大佬的文章~
每日一言
I love you for my life past.
我爱你，爱了整整一个曾经