diff options
Diffstat (limited to 'design_linked_list.py')
-rw-r--r-- | design_linked_list.py | 107 |
1 files changed, 107 insertions, 0 deletions
diff --git a/design_linked_list.py b/design_linked_list.py new file mode 100644 index 0000000..0ef176d --- /dev/null +++ b/design_linked_list.py @@ -0,0 +1,107 @@ +# 707. Design Linked List + +""" +design your implementation of the linked list. you can choose to use a singly +or doubly linked list. a node in a singly linked list should have two +attributes: 'val' and 'next'. 'val' is the value of the current node, and +'next' is a pointing/reference to the next code. if you want to use the +doubly linked list, you will need one more attribute 'prev' to indicate the +previous node in the linked list. assume all nodes in the linked list are +0-indexed to indicate the previous node in the linked list. assume all nodes +in the linked list are 0-indexed. +""" + + +class Node(object): + def __init__(self, val): + self.val = val + self.next = None + + +class MyLinkedList(object): + def __init__(self): + self.head = None + self.size = 0 + + def get(self, index): + """ + :type index: int + :rtype: int + """ + if index < 0 or index >= self.size: + return -1 + if self.head is None: + return -1 + curr = self.head + for i in range(index): + curr = curr.next + return curr.val + + def addAtHead(self, val): + """ + :type val: int + :rtype: None + """ + node = Node(val) + node.next = self.head + self.head = node + self.size += 1 + + def addAtTail(self, val): + """ + :type val: int + :rtype: None + """ + curr = self.head + if curr is None: + self.head = Node(val) + else: + while curr.next is not None: + curr = curr.next + curr.next = Node(val) + self.size += 1 + + def addAtIndex(self, index, val): + """ + :type index: int + :type val: int + :rtype: None + """ + if index < 0 or index > self.size: + return + if index == 0: + self.addAtHead(val) + else: + curr = self.head + for i in range(index - 1): + curr = curr.next + node = Node(val) + node.next = curr.next + curr.next = node + self.size += 1 + + def deleteAtIndex(self, index): + """ + :type index: int + :rtype: None + """ + if index < 0 or index >= self.size: + return + curr = self.head + if index == 0: + self.head = curr.next + else: + for i in range(index - 1): + curr = curr.next + curr.next = curr.next.next + self.size -= 1 + + +if __name__ == "__main__": + obj = MyLinkedList() + obj.addAtHead(1) + obj.addAtTail(3) + obj.addAtIndex(1, 2) + print(obj.get(1)) + obj.deleteAtIndex(1) + print(obj.get(1)) |