Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class LLNode:
- '''Node to be used in linked list
- nxt: LLNode -- next node
- None iff we're at end of list
- value: object --- data for current node
- '''
- def __init__(self, value, nxt=None):
- ''' (LLNode, object, LLNode) -> NoneType
- Create LLNode (self) with data value and successor nxt.
- '''
- self.value, self.nxt = value, nxt
- def __repr__(self):
- ''' (LLNode) -> str
- Return a string representation of LLNode (self) that can yields
- an equivalent LLNode if evaluated in Python.
- >>> n = LLNode(5, LLNode(7))
- >>> n.nxt
- LLNode(7)
- >>> n
- LLNode(5, LLNode(7))
- '''
- if self.nxt is None:
- return 'LLNode({})'.format(repr(self.value))
- else:
- return 'LLNode({}, {})'.format(repr(self.value), repr(self.nxt))
- def __str__(self):
- ''' (LLNode) -> str
- Return a user-friendly representation of this LLNode.
- >>> n = LLNode(5, LLNode(7))
- >>> print(n)
- 5 -> 7 ->|
- '''
- if self.nxt is None:
- return '{} ->|'.format(str(self.value))
- else:
- return '{} -> {}'.format(str(self.value), str(self.nxt))
- def __eq__(self, other):
- ''' (LLNode, object) -> bool
- Return whether LLNode (self) is equivalent to other.
- >>> LLNode(5).__eq__(5)
- False
- >>> n = LLNode(5, LLNode(7))
- >>> n2 = LLNode(5, LLNode(7, None))
- >>> n.__eq__(n2)
- True
- '''
- return (type(self) == type(other) and
- (self.value, self.nxt) == (other.value, other.nxt))
- class LinkedList:
- '''Collection of LLNodes organized into a linked list.
- front: LLNode -- front of list
- back: LLNode -- back of list'''
- def __init__(self):
- ''' (LinkedList) -> NoneType
- Create an empty linked list.
- '''
- self.front, self.back = None, None
- self.size = 0
- def __str__(self):
- ''' (LinkedList) -> str
- Return a human-friendly string representation of
- LinkedList (self)
- >>> lnk = LinkedList()
- >>> lnk.prepend(5)
- >>> print(lnk)
- 5 ->|
- '''
- return str(self.front)
- def __eq__(self, other):
- ''' (LinkedList, object) -> bool
- Return whether LinkedList (self) is equivalent to
- other.
- >>> LinkedList().__eq__(None)
- False
- >>> lnk = LinkedList()
- >>> lnk.prepend(5)
- >>> lnk2 = LinkedList()
- >>> lnk2.prepend(5)
- >>> lnk.__eq__(lnk2)
- True
- '''
- return (type(self) == type(other) and
- (self.size, self.front) == (other.size, other.front))
- def append(lnk, value):
- ''' (LinkedList, object) -> NoneType
- Insert a new node with value at back of lnk.
- >>> lnk = LinkedList()
- >>> lnk.append(5)
- >>> lnk.size
- 1
- >>> print(lnk.front)
- 5 ->|
- >>> lnk.append(6)
- >>> lnk.size
- 2
- >>> print(lnk.front)
- 5 -> 6 ->|
- '''
- new_node = LLNode(value)
- if lnk.back:
- lnk.back.nxt = new_node
- lnk.back = new_node
- else:
- lnk.back = lnk.front = new_node
- lnk.size += 1
- def prepend(self, value):
- ''' (LinkedList, object) -> Nonetype
- Insert value at front of LLNode (self).
- >>> lnk = LinkedList()
- >>> lnk.prepend(0)
- >>> lnk.prepend(1)
- >>> lnk.prepend(2)
- >>> str(lnk.front)
- '2 -> 1 -> 0 ->|'
- >>> lnk.size
- 3
- '''
- self.front = LLNode(value, self.front)
- if self.back is None:
- self.back = self.front
- self.size += 1
- def delete_front(self):
- ''' (LinkedList) -> NoneType
- Delete front node from LinkedList (self).
- self.front must not be None
- >>> lnk = LinkedList()
- >>> lnk.prepend(0)
- >>> lnk.prepend(1)
- >>> lnk.prepend(2)
- >>> lnk.delete_front()
- >>> str(lnk.front)
- '1 -> 0 ->|'
- >>> lnk.size
- 2
- '''
- self.front = self.front.nxt
- self.size -= 1
- def __getitem__(self, index):
- ''' (LinkedList, int|slice) -> object
- Return the value at position index.
- # don't fuss about slices yet.
- >>> lnk = LinkedList()
- >>> lnk.prepend(1)
- >>> lnk.prepend(0)
- >>> lnk.__getitem__(1)
- 1
- '''
- if index > self.size - 1:
- raise Exception('out of range')
- else:
- current_node = self.front
- for i in range(0, index):
- current_node = current_node.nxt
- return current_node.value
- def __setitem__(self, index, value):
- ''' (LinkedList, int|slice, object) -> NoneType
- Set the value at index to value, if index is in range, otherwise
- raise an IndexError. Indexs are counted from 0. Note that negative
- integers can be adjusted by adding self.size, to get a index in
- range.
- >>> lnk = LinkedList()
- >>> lnk.prepend(5)
- >>> lnk.prepend(7)
- >>> lnk.__setitem__(1, 9)
- >>> print(lnk.front)
- 7 -> 9 ->|
- >>> lnk[0] = 3
- >>> print(lnk.front)
- 3 -> 9 ->|
- >>> lnk[-1] = 8
- >>> print(lnk.front)
- 3 -> 8 ->|
- '''
- fixed_index = index if (index >= 0) else (index + self.size)
- if fixed_index > self.size:
- raise IndexError
- else:
- current_node = self.front
- for n in range(fixed_index):
- current_node = current_node.nxt
- current_node.value = value
- def __contains__(self, value):
- ''' (LinkedList, object) -> bool
- Return whether LinkedList (self) contains value.
- >>> lnk = LinkedList()
- >>> lnk.prepend(0)
- >>> lnk.prepend(1)
- >>> lnk.prepend(2)
- >>> lnk.__contains__(1)
- True
- >>> lnk.__contains__(3)
- False
- '''
- current_node = self.front
- while current_node:
- if value == current_node.value:
- return True
- current_node = current_node.nxt
- return False
- def __add__(self, other):
- ''' (LinkedList, LinkedList) -> LinkedList
- Concatenate LinkedList (self) to LinkedList (other) and
- return a new list, leaving self and other unchanged.
- >>> lnk1 = LinkedList()
- >>> lnk1.prepend(5)
- >>> lnk2 = LinkedList()
- >>> lnk2.prepend(7)
- >>> lnk3 = lnk1.__add__(lnk2)
- >>> print(lnk3.front)
- 5 -> 7 ->|
- >>> print(lnk1.front)
- 5 ->|
- >>> print(lnk2.front)
- 7 ->|
- '''
- new_llst = LinkedList()
- new_llst.append((self.front).value)
- next_link = (self.front).nxt.value if (self.front).nxt else None
- while next_link:
- new_llst.append(next_link)
- next_link = (self.front).nxt.value if (self.front).nxt else None
- new_llst.append((other.front).value)
- next_link = (other.front).nxt.value if (other.front).nxt else None
- while next_link:
- new_llst.append(next_link)
- next_link = (other.front).nxt.value if (other.front).nxt else None
- new_llst.size = self.size + other.size
- return new_llst
- def insert_before(lnk, v1, v2):
- ''' (LinkedList, object) -> NoneType
- Insert a new node with value v1 before the first occurrence
- of a node with value v2. Do nothing if no node has value
- v2.
- >>> lnk = LinkedList()
- >>> lnk.prepend(5)
- >>> insert_before(lnk, 4, 5)
- >>> print(lnk.front)
- 4 -> 5 ->|
- >>> insert_before(lnk, 3, 5)
- >>> print(lnk.front)
- 4 -> 3 -> 5 ->|
- >>> insert_before(lnk, 3, 7)
- >>> print(lnk)
- 4 -> 3 -> 5 ->|
- '''
- new_node = LLNode(v1)
- current_node = lnk.front
- if not current_node:
- pass
- elif current_node.value == v2:
- new_node.nxt = current_node
- lnk.front = new_node
- else:
- n = 0
- while current_node.nxt and n == 0:
- if current_node.nxt.value == v2:
- new_node.nxt = current_node.nxt
- current_node.nxt = new_node
- n = 1
- current_node = current_node.nxt
- def delete_after(lnk, value):
- ''' (LinkedList, object) -> NoneType
- Insert a new node with value after the first occurrence of a
- node containing value, if possible.
- >>> lnk = LinkedList()
- >>> lnk.append(3)
- >>> lnk.append(5)
- >>> lnk.append(7)
- >>> lnk.append(9)
- >>> delete_after(lnk, 3)
- >>> print(lnk)
- 3 -> 7 -> 9 ->|
- >>> delete_after(lnk, 7)
- >>> print(lnk)
- 3 -> 7 ->|
- >>> delete_after(lnk, 15)
- >>> print(lnk)
- 3 -> 7 ->|
- '''
- n = 0
- current_node = lnk.front
- while n == 0 and current_node.nxt:
- if current_node.value == value:
- current_node.nxt = (current_node.nxt).nxt
- lnk.size -= 1
- n = 1
- current_node = current_node.nxt
- def delete_back(lnk):
- ''' (LinkedList) -> NoneType
- Delete back node of lnk, if it exists, otherwise
- do nothing.
- >>> lnk = LinkedList()
- >>> lnk.prepend(5)
- >>> lnk.prepend(7)
- >>> print(lnk.front)
- 7 -> 5 ->|
- >>> delete_back(lnk)
- >>> lnk.size
- 1
- >>> print(lnk.front)
- 7 ->|
- >>> delete_back(lnk)
- >>> lnk.size
- 0
- >>> print(lnk.front)
- None
- '''
- if lnk.size > 0:
- prev_node, cur_node = None, lnk.front
- # walk along until cur_node is lnk.back
- while not cur_node.nxt is None:
- prev_node = cur_node
- cur_node = cur_node.nxt
- lnk.back = prev_node
- if lnk.back is None:
- lnk.front = None
- else:
- lnk.back.nxt = None
- lnk.size -= 1
- def odd_nodes(lnk):
- ''' (LinkedList) -> LinkedList
- Return a new linked list with values of odd-indexed nodes of lnk.
- >>> lnk = LinkedList()
- >>> lnk.append(3)
- >>> lnk.append(5)
- >>> lnk.append(7)
- >>> lnk.append(9)
- >>> lnk2 = odd_nodes(lnk)
- >>> print(lnk2)
- 5 -> 9 ->|
- '''
- new_linked_list = LinkedList()
- n = 0
- for n in range(lnk.size):
- if n % 2 == 1:
- new_linked_list.append(lnk[n])
- return new_linked_list
- def filter_nodes(lnk, f):
- ''' (LinkedList, function) -> LinkedList
- Return a new linked list with values of lnk for
- nodes that satisfy boolean-valued function f.
- >>> lnk = LinkedList()
- >>> lnk.append(3)
- >>> lnk.append(4)
- >>> lnk.append(5)
- >>> lnk.append(6)
- >>> def f(node): return node.value % 2 == 0
- >>> lnk2 = filter_nodes(lnk, f)
- >>> print(lnk2)
- 4 -> 6 ->|
- '''
- new_list, cur_node = LinkedList(), lnk.front
- while cur_node:
- if f(cur_node):
- new_list.append(cur_node.value)
- cur_node = cur_node.nxt
- return new_list
- if __name__ == '__main__':
- import doctest
- doctest.testmod()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement