Convert linked list to list python

Inserting a new node at the beginning of a list is probably the most straightforward insertion since you don’t have to traverse the whole list to do it. It’s all about creating a new node and then pointing the head of the list to it.

Have a look at the following implementation of add_first() for the class LinkedList:

def add_first(self, node): node.next = self.head self.head = node

In the above example, you’re setting self.head as the next reference of the new node so that the new node points to the old self.head. After that, you need to state that the new head of the list is the inserted node.

Here’s how it behaves with a sample list:

>>>>>> llist = LinkedList() >>> llist None >>> llist.add_first(Node("b")) >>> llist b -> None >>> llist.add_first(Node("a")) >>> llist a -> b -> None

As you can see, add_first() always adds the node to the head of the list, even if the list was empty before.

Inserting a new node at the end of the list forces you to traverse the whole linked list first and to add the new node when you reach the end. You can’t just append to the end as you would with a normal list because in a linked list you don’t know which node is last.

Here’s an example implementation of a function for inserting a node to the end of a linked list:

def add_last(self, node): if self.head is None: self.head = node return for current_node in self: pass current_node.next = node

First, you want to traverse the whole list until you reach the end (that is, until the for loop raises a StopIteration exception). Next, you want to set the current_node as the last node on the list. Finally, you want to add the new node as the next value of that current_node.

Here’s an example of add_last() in action:

>>>>>> llist = LinkedList(["a", "b", "c", "d"]) >>> llist a -> b -> c -> d -> None >>> llist.add_last(Node("e")) >>> llist a -> b -> c -> d -> e -> None >>> llist.add_last(Node("f")) >>> llist a -> b -> c -> d -> e -> f -> None

In the code above, you start by creating a list with four values (a, b, c, and d). Then, when you add new nodes using add_last(), you can see that the nodes are always appended to the end of the list.

Inserting between two nodes adds yet another layer of complexity to the linked list’s already complex insertions because there are two different approaches that you can use:

1. Inserting after an existing node
2. Inserting before an existing node

It might seem weird to split these into two methods, but linked lists behave differently than normal lists, and you need a different implementation for each case.

Here’s a method that adds a node after an existing node with a specific data value:

def add_after(self, target_node_data, new_node): if self.head is None: raise Exception("List is empty") for node in self: if node.data == target_node_data: new_node.next = node.next node.next = new_node return raise Exception("Node with data '%s' not found" % target_node_data)

In the above code, you’re traversing the linked list looking for the node with data indicating where you want to insert a new node. When you find the node you’re looking for, you’ll insert the new node immediately after it and rewire the next reference to maintain the consistency of the list.

The only exceptions are if the list is empty, making it impossible to insert a new node after an existing node, or if the list does not contain the value you’re searching for. Here are a few examples of how add_after() behaves:

>>>>>> llist = LinkedList() >>> llist.add_after("a", Node("b")) Exception: List is empty >>> llist = LinkedList(["a", "b", "c", "d"]) >>> llist a -> b -> c -> d -> None >>> llist.add_after("c", Node("cc")) >>> llist a -> b -> c -> cc -> d -> None >>> llist.add_after("f", Node("g")) Exception: Node with data 'f' not found

Trying to use add_after() on an empty list results in an exception. The same happens when you try to add after a nonexistent node. Everything else works as expected.

Now, if you want to implement add_before(), then it will look something like this:

1def add_before(self, target_node_data, new_node): 2 if self.head is None: 3 raise Exception("List is empty") 4 5 if self.head.data == target_node_data: 6 return self.add_first(new_node) 7 8 prev_node = self.head 9 for node in self: 10 if node.data == target_node_data: 11 prev_node.next = new_node 12 new_node.next = node 13 return 14 prev_node = node 15 16 raise Exception("Node with data '%s' not found" % target_node_data)

There are a few things to keep in mind while implementing the above. First, as with add_after(), you want to make sure to raise an exception if the linked list is empty (line 2) or the node you’re looking for is not present (line 16).

Second, if you’re trying to add a new node before the head of the list (line 5), then you can reuse add_first() because the node you’re inserting will be the new head of the list.

Finally, for any other case (line 9), you should keep track of the last-checked node using the prev_node variable. Then, when you find the target node, you can use that prev_node variable to rewire the next values.

Once again, an example is worth a thousand words:

>>>>>> llist = LinkedList() >>> llist.add_before("a", Node("a")) Exception: List is empty >>> llist = LinkedList(["b", "c"]) >>> llist b -> c -> None >>> llist.add_before("b", Node("a")) >>> llist a -> b -> c -> None >>> llist.add_before("b", Node("aa")) >>> llist.add_before("c", Node("bb")) >>> llist a -> aa -> b -> bb -> c -> None >>> llist.add_before("n", Node("m")) Exception: Node with data 'n' not found

With add_before(), you now have all the methods you need to insert nodes anywhere you’d like in your list.