Reputation: 133
I am doing self study on Linked Lists with Python. I'm trying to grapple with trying to visualize the structure and concept of linked lists. Below is code from self study that is asking for me to add the missing code. Can some one please draw out or explain how I should picture this. I am familiar with regular python lists, dict, and other common data structures. But for example for the method my thought process is
if current:
return current.value
else:
return None
But this is incorrect. Am I checking that the constructor initialized a list and has a element variable current? Below is full code. Thank you.
"""The LinkedList code from before is provided below.
Add three functions to the LinkedList.
"get_position" returns the element at a certain position.
The "insert" function will add an element to a particular
spot in the list.
"delete" will delete the first element with that
particular value.
Then, use "Test Run" and "Submit" to run the test cases
at the bottom."""
class Element(object):
def __init__(self, value):
self.value = value
self.next = None
class LinkedList(object):
def __init__(self, head=None):
self.head = head
def append(self, new_element):
current = self.head
if self.head:
while current.next:
current = current.next
current.next = new_element
else:
self.head = new_element
def get_position(self, position):
"""Get an element from a particular position.
Assume the first position is "1".
Return "None" if position is not in the list."""
return None
def insert(self, new_element, position):
"""Insert a new node at the given position.
Assume the first position is "1".
Inserting at position 3 means between
the 2nd and 3rd elements."""
pass
def delete(self, value):
"""Delete the first node with a given value."""
pass
# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)
# Start setting up a LinkedList
ll = LinkedList(e1)
ll.append(e2)
ll.append(e3)
# Test get_position
# Should print 3
print ll.head.next.next.value
# Should also print 3
print ll.get_position(3).value
# Test insert
ll.insert(e4,3)
# Should print 4 now
print ll.get_position(3).value
# Test delete
ll.delete(1)
# Should print 2 now
print ll.get_position(1).value
# Should print 4 now
print ll.get_position(2).value
# Should print 3 now
print ll.get_position(3).value
Upvotes: 3
Views: 2103
Reputation: 90
All you need to do:
Firstly, try to visualize what will be happening while changing this state to that, or like- write the whole visualization on a paper or even in any online software to understand the changes.
Lastly/Finally, make sure that you know the core concept of linked-lists and do some tricky, bunch of different operation with it. Or, you may search on Google for a couple of resources.
Well, here is the solution I did for your problem:
class Element(object): def __init__(self, value): self.value = value self.next = None class LinkedList(object): def __init__(self, head=None): self.head = head def append(self, new_element): current = self.head if self.head: while current.next: current = current.next current.next = new_element else: self.head = new_element def get_position(self, position): counter = 1 current = self.head if position < 1: return None while current and counter <= position: if counter == position: return current current = current.next counter += 1 return None def insert(self, new_element, position): counter = 1 current = self.head if position > 1: while current and counter < position: if counter == position - 1: new_element.next = current.next current.next = new_element current = current.next counter += 1 elif position == 1: new_element.next = self.head self.head = new_element def delete(self, value): current = self.head previous = None while current.value != value and current.next: previous = current current = current.next if current.value == value: if previous: previous.next = current.next else: self.head = current.next # Test cases # Set up some Elements e1 = Element(1) e2 = Element(2) e3 = Element(3) e4 = Element(4) # Start setting up a LinkedList ll = LinkedList(e1) ll.append(e2) ll.append(e3) # Test get_position # Should print 3 print(ll.head.next.next.value) # Should also print 3 print(ll.get_position(3).value) # Test insert ll.insert(e4,3) # Should print 4 now print(ll.get_position(3).value) # Test delete ll.delete(1) # Should print 2 now print(ll.get_position(1).value) # Should print 4 now print(ll.get_position(2).value) # Should print 3 now print(ll.get_position(3).value)
Again, any further problem; take a paper, write the code and visualize what's happening.
Upvotes: 1
Reputation: 10819
for the method my thought process is...
What method? get_position
? insert
? delete
?
As @JacobIRR suggested, adding a way of printing your linked list can be helpful. Take a look:
class Element:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, value):
element = Element(value)
if self.head is None:
self.head = element
return
cursor = self.head
while cursor.next is not None:
cursor = cursor.next
cursor.next = element
def __str__(self):
values = []
cursor = self.head
while cursor is not None:
values.append(cursor.value)
cursor = cursor.next
return " -> ".join(values)
def main():
linked_list = LinkedList()
linked_list.append("Foo")
linked_list.append("Bar")
linked_list.append("Fizz")
linked_list.append("Buzz")
print(linked_list)
return 0
if __name__ == "__main__":
import sys
sys.exit(main())
Output:
Foo -> Bar -> Fizz -> Buzz
Upvotes: 1