Skip to content

Instantly share code, notes, and snippets.

@davidrpugh

davidrpugh/linked_list.py

Last active March 7, 2016 07:19
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save davidrpugh/67686542d49fa6f00cd5 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save davidrpugh/67686542d49fa6f00cd5 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. davidrpugh revised this gist Mar 7, 2016. 1 changed file with 22 additions and 0 deletions.
    22 changes: 22 additions & 0 deletions stack.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,22 @@
    import linked_list


    class Stack(object):
    """Simple implementation of a LIFO container using a LinkedList."""

    _linked_list = linked_list.LinkedList()

    def peek(self):
    """Return the value from the top of the Stack."""
    return self._linked_list[0]

    def pop(self):
    """O(1) Removal (and return) of the value from the top of the Stack."""
    value = self.peek()
    self._linked_list.remove_head()
    return value

    def push(self, value):
    """O(1) insertion of data onto the top of the Stack."""
    self._linked_list.prepend(value)

  2. davidrpugh revised this gist Mar 7, 2016. 1 changed file with 4 additions and 3 deletions.
    7 changes: 4 additions & 3 deletions linked_list.py
    View file
    Original file line number Diff line number Diff line change
    @@ -91,7 +91,7 @@ def prepend(self, value):

    def append(self, value):
    """
    O(n) insertion of data onto the tail of the LinkedList.
    O(1) insertion of data onto the tail of the LinkedList.

    Notes
    -----
    @@ -104,8 +104,9 @@ def append(self, value):
    self._tail = self.Node(value, None)
    self._head = self._tail
    else:
    predecessor = self._find_predecessor(self._tail.value)
    self._tail = self.Node(value, predecessor)
    new_node = self.Node(value, None)
    self._tail.next = new_node
    self._tail = new_node
    self._length += 1 # SIDE EFFECT!

    def remove(self, value):
  3. davidrpugh revised this gist Mar 7, 2016. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions linked_list.py
    View file
    Original file line number Diff line number Diff line change
    @@ -7,6 +7,8 @@ class LinkedList(Sequence):
    _length = 0

    _head = None

    _tail = None

    class Node(object):
    """Represents an individual node in a LinkedList"""
  4. davidrpugh revised this gist Mar 7, 2016. 1 changed file with 1 addition and 2 deletions.
    3 changes: 1 addition & 2 deletions linked_list.py
    View file
    Original file line number Diff line number Diff line change
    @@ -102,8 +102,7 @@ def append(self, value):
    self._tail = self.Node(value, None)
    self._head = self._tail
    else:
    current_tail_value = self._tail.value
    predecessor = self._find_predecessor(current_tail_value)
    predecessor = self._find_predecessor(self._tail.value)
    self._tail = self.Node(value, predecessor)
    self._length += 1 # SIDE EFFECT!

  5. davidrpugh revised this gist Mar 7, 2016. 1 changed file with 42 additions and 9 deletions.
    51 changes: 42 additions & 9 deletions linked_list.py
    View file
    Original file line number Diff line number Diff line change
    @@ -7,7 +7,7 @@ class LinkedList(Sequence):
    _length = 0

    _head = None

    class Node(object):
    """Represents an individual node in a LinkedList"""

    @@ -69,24 +69,45 @@ def _find_predecessor(self, value):
    current_node = current_node.next
    return predecessor

    def insert(self, value):
    def prepend(self, value):
    """
    O(1) insertion of some data into the LinkedList.
    O(1) insertion of data onto the head of the LinkedList.

    Notes
    -----
    Inserting a new value into the linked list increments the
    Inserting a new value into the LinkedList increments the
    private _length property. This side effect allows us to compute
    the length of a linked list is O(1).

    """
    if self._head is None:
    self._head = self.Node(value, None)
    self._tail = self._head
    else:
    self._head = self.Node(value, self._head)
    self._length += 1 # SIDE EFFECT!

    def append(self, value):
    """
    O(n) insertion of data onto the tail of the LinkedList.

    Notes
    -----
    Inserting a new value into the linked list increments the
    private _length property. This side effect allows us to compute
    the length of a linked list is O(1).

    """
    if self._tail is None:
    self._tail = self.Node(value, None)
    self._head = self._tail
    else:
    current_tail_value = self._tail.value
    predecessor = self._find_predecessor(current_tail_value)
    self._tail = self.Node(value, predecessor)
    self._length += 1 # SIDE EFFECT!

    def delete(self, value):
    def remove(self, value):
    """
    O(n) removal of some data from the LinkedList.

    @@ -98,14 +119,26 @@ def delete(self, value):

    """
    if value == self._head.value:
    deleted_node = self._head
    self._head = deleted_node.next
    self._length -= 1 # SIDE EFFECT!
    self.remove_head()
    else:
    predecessor = self._find_predecessor(value)
    if predecessor is not None:
    deleted_node = predecessor.next
    predecessor.next = deleted_node.next
    self._length -= 1 # SIDE EFFECT!
    else:
    raise ValueError("Data item is not in the LinkedList!")
    raise ValueError("Item is not in the LinkedList!")

    def remove_head(self):
    """O(1) removal of the head of a LinkedList."""
    if self._head is not None:
    self._head = self._head.next
    self._length -= 1 # SIDE EFFECT!

    def remove_tail(self):
    """O(n) removal of the tail of a LinkedList."""
    if self._tail is not None:
    predecessor = self._find_predecessor(self._tail.value)
    predecessor.next = None
    self._tail = predecessor
    self._length -= 1 # SIDE EFFECT!
  6. davidrpugh revised this gist Mar 7, 2016. 1 changed file with 0 additions and 1 deletion.
    1 change: 0 additions & 1 deletion linked_list.py
    View file
    Original file line number Diff line number Diff line change
    @@ -85,7 +85,6 @@ def insert(self, value):
    else:
    self._head = self.Node(value, self._head)
    self._length += 1 # SIDE EFFECT!


    def delete(self, value):
    """
  7. davidrpugh revised this gist Mar 7, 2016. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions linked_list.py
    View file
    Original file line number Diff line number Diff line change
    @@ -48,7 +48,7 @@ def __str__(self):
    out += "None"
    return out

    def _find_predecessor(self, node, value):
    def _find_predecessor(self, value):
    """
    O(n) traversal of the LinkedList to find the predecessor of the node
    containing a particular value of data.
    @@ -103,7 +103,7 @@ def delete(self, value):
    self._head = deleted_node.next
    self._length -= 1 # SIDE EFFECT!
    else:
    predecessor = self._find_predecessor(self._head, value)
    predecessor = self._find_predecessor(value)
    if predecessor is not None:
    deleted_node = predecessor.next
    predecessor.next = deleted_node.next
  8. davidrpugh revised this gist Mar 7, 2016. 1 changed file with 10 additions and 8 deletions.
    18 changes: 10 additions & 8 deletions linked_list.py
    View file
    Original file line number Diff line number Diff line change
    @@ -48,8 +48,7 @@ def __str__(self):
    out += "None"
    return out

    @classmethod
    def _find_predecessor(cls, node, value):
    def _find_predecessor(self, node, value):
    """
    O(n) traversal of the LinkedList to find the predecessor of the node
    containing a particular value of data.
    @@ -60,12 +59,15 @@ def _find_predecessor(cls, node, value):
    from a LinkedList.

    """
    if node.next is None:
    return None
    elif node.next.value == value:
    return node
    else:
    return cls._find_predecessor(node.next, value)
    predecessor = None
    current_node = self._head
    while current_node.next is not None:
    if current_node.next.value == value:
    predecessor = current_node
    break
    else:
    current_node = current_node.next
    return predecessor

    def insert(self, value):
    """
  9. davidrpugh revised this gist Mar 6, 2016. 1 changed file with 19 additions and 19 deletions.
    38 changes: 19 additions & 19 deletions linked_list.py
    View file
    Original file line number Diff line number Diff line change
    @@ -6,7 +6,7 @@ class LinkedList(Sequence):

    _length = 0

    head = None
    _head = None

    class Node(object):
    """Represents an individual node in a LinkedList"""
    @@ -20,7 +20,7 @@ def __getitem__(self, key):
    if key >= self._length:
    raise IndexError("Index out of bounds.")
    else:
    current_node = self.head
    current_node = self._head
    for i in range(key):
    current_node = current_node.next
    return current_node.value
    @@ -31,17 +31,17 @@ def __len__(self):

    Notes
    -----
    Access to the length of the LinkedList is O(1) because we increment the
    value of the private_length attribute on every insertion and decrement
    the value of _length on every deletion.
    Access to the length of the LinkedList is O(1) because we
    increment the value of the private_length attribute on every insertion
    and decrement the value of _length on every deletion.

    """
    return self._length

    def __str__(self):
    """Human readable string representation of a LinkedList"""
    out = ""
    current_node = self.head
    current_node = self._head
    while current_node is not None:
    out += str(current_node.value) + " -> "
    current_node = current_node.next
    @@ -73,15 +73,15 @@ def insert(self, value):

    Notes
    -----
    Inserting a new value into the linked list increments the private
    _length property. This side effect allows us to compute the length of a
    linked list is O(1).
    Inserting a new value into the linked list increments the
    private _length property. This side effect allows us to compute
    the length of a linked list is O(1).

    """
    if self.head is None:
    self.head = self.Node(value, None)
    if self._head is None:
    self._head = self.Node(value, None)
    else:
    self.head = self.Node(value, self.head)
    self._head = self.Node(value, self._head)
    self._length += 1 # SIDE EFFECT!


    @@ -91,17 +91,17 @@ def delete(self, value):

    Notes
    -----
    Removing an existing value from the linked list decrements the private
    _length property. This side effect allows us to compute the length of a
    linked list is O(1).
    Removing an existing value from the linked list decrements the
    private _length property. This side effect allows us to compute
    the length of a linked list is O(1).

    """
    if value == self.head.value:
    deleted_node = self.head
    self.head = deleted_node.next
    if value == self._head.value:
    deleted_node = self._head
    self._head = deleted_node.next
    self._length -= 1 # SIDE EFFECT!
    else:
    predecessor = self._find_predecessor(self.head, value)
    predecessor = self._find_predecessor(self._head, value)
    if predecessor is not None:
    deleted_node = predecessor.next
    predecessor.next = deleted_node.next
  10. davidrpugh revised this gist Mar 6, 2016. 1 changed file with 77 additions and 18 deletions.
    95 changes: 77 additions & 18 deletions linked_list.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,51 +1,110 @@
    class LinkedList(object):
    from collections.abc import Sequence


    class LinkedList(Sequence):
    """Simple implementation of a linked list."""

    _length = 0

    head = None

    class Node(object):
    """Represents an individual node in a LinkedList"""

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

    def __getitem__(self, key):
    """O(n) access to data item given its key (or index)."""
    if key >= self._length:
    raise IndexError("Index out of bounds.")
    else:
    current_node = self.head
    for i in range(key):
    current_node = current_node.next
    return current_node.value

    def __len__(self):
    """
    O(1) access to the length of the LinkedList.

    Notes
    -----
    Access to the length of the LinkedList is O(1) because we increment the
    value of the private_length attribute on every insertion and decrement
    the value of _length on every deletion.

    """
    return self._length

    def __str__(self):
    """Human readable string representation of a LinkedList"""
    out = ""
    current_node = self.head
    while current_node is not None:
    out += str(current_node.data) + " -> "
    out += str(current_node.value) + " -> "
    current_node = current_node.next
    out += "None"
    return out

    @classmethod
    def _find_predecessor(cls, node, data):
    """Find the predecessor of a node containing some data."""
    def _find_predecessor(cls, node, value):
    """
    O(n) traversal of the LinkedList to find the predecessor of the node
    containing a particular value of data.

    Notes
    -----
    Finding the predecessor node is the burdensome part of removing data
    from a LinkedList.

    """
    if node.next is None:
    return None
    elif node.next.data == data:
    elif node.next.value == value:
    return node
    else:
    return cls._find_predecessor(node.next, data)

    def insert(self, data):
    """O(1) insertion of some data into the LinkedList."""
    return cls._find_predecessor(node.next, value)

    def insert(self, value):
    """
    O(1) insertion of some data into the LinkedList.

    Notes
    -----
    Inserting a new value into the linked list increments the private
    _length property. This side effect allows us to compute the length of a
    linked list is O(1).

    """
    if self.head is None:
    self.head = self.Node(data, None)
    self.head = self.Node(value, None)
    else:
    self.head = self.Node(data, self.head)
    self.head = self.Node(value, self.head)
    self._length += 1 # SIDE EFFECT!


    def delete(self, value):
    """
    O(n) removal of some data from the LinkedList.

    Notes
    -----
    Removing an existing value from the linked list decrements the private
    _length property. This side effect allows us to compute the length of a
    linked list is O(1).

    def delete(self, data):
    """O(n) removal of some data from the LinkedList."""
    if data == self.head.data:
    """
    if value == self.head.value:
    deleted_node = self.head
    self.head = deleted_node.next
    self._length -= 1 # SIDE EFFECT!
    else:
    predecessor = self._find_predecessor(self.head, data)
    predecessor = self._find_predecessor(self.head, value)
    if predecessor is not None:
    deleted_node = predecessor.next
    predecessor.next = deleted_node.next
    self._length -= 1 # SIDE EFFECT!
    else:
    raise ValueError("Data item is not in the LinkedList!")
  11. davidrpugh created this gist Mar 2, 2016.
    51 changes: 51 additions & 0 deletions linked_list.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,51 @@
    class LinkedList(object):
    """Simple implementation of a linked list."""

    head = None

    class Node(object):
    """Represents an individual node in a LinkedList"""

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

    def __str__(self):
    """Human readable string representation of a LinkedList"""
    out = ""
    current_node = self.head
    while current_node is not None:
    out += str(current_node.data) + " -> "
    current_node = current_node.next
    out += "None"
    return out

    @classmethod
    def _find_predecessor(cls, node, data):
    """Find the predecessor of a node containing some data."""
    if node.next is None:
    return None
    elif node.next.data == data:
    return node
    else:
    return cls._find_predecessor(node.next, data)

    def insert(self, data):
    """O(1) insertion of some data into the LinkedList."""
    if self.head is None:
    self.head = self.Node(data, None)
    else:
    self.head = self.Node(data, self.head)

    def delete(self, data):
    """O(n) removal of some data from the LinkedList."""
    if data == self.head.data:
    deleted_node = self.head
    self.head = deleted_node.next
    else:
    predecessor = self._find_predecessor(self.head, data)
    if predecessor is not None:
    deleted_node = predecessor.next
    predecessor.next = deleted_node.next
    else:
    raise ValueError("Data item is not in the LinkedList!")