Understanding Linked List with Python

Question

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

I would suggest making a print_list function that prints out a set of linked list nodes like this: 1->2->3->4 so you can call this function whenever you like to help visualize the state of the list. — JacobIRR
– JacobIRR, Commented Aug 2, 2019 at 18:37

Paul M. · Accepted Answer · 2019-08-03 11:34:56Z

1

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

edited Aug 3, 2019 at 11:34

answered Aug 2, 2019 at 19:23

Paul M.

10.8k2 gold badges11 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

pylang Over a year ago

What @user... has done here is add a type of "traverse" operation to __repr__, which is very helpful in many situations. It is worth abstracting this into a separate method as you'll find you may use it again later.

halfer · Accepted Answer · 2020-07-03 14:10:59Z

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.

Collectives™ on Stack Overflow

Understanding Linked List with Python

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related