aboutsummaryrefslogtreecommitdiff
path: root/design_linked_list.py
diff options
context:
space:
mode:
Diffstat (limited to 'design_linked_list.py')
-rw-r--r--design_linked_list.py107
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))