Python Linked List

Python Linked List

Here is some list functions based on Martin v. Löwis's representation:

cons   = lambda el, lst: (el, lst)
mklist = lambda *args: reduce(lambda lst, el: cons(el, lst), reversed(args), None)
car = lambda lst: lst[0] if lst else lst
cdr = lambda lst: lst[1] if lst else lst
nth = lambda n, lst: nth(n-1, cdr(lst)) if n > 0 else car(lst)
length = lambda lst, count=0: length(cdr(lst), count+1) if lst else count
begin = lambda *args: args[-1]
display = lambda lst: begin(w("%s " % car(lst)), display(cdr(lst))) if lst else w("nil\n")

where w = sys.stdout.write

Although doubly linked lists are famously used in Raymond Hettinger's ordered set recipe, singly linked lists have no practical value in Python.

I've never used a singly linked list in Python for any problem except educational.

Thomas Watnedal suggested a good educational resource How to Think Like a Computer Scientist, Chapter 17: Linked lists:

A linked list is either:

  • the empty list, represented by None, or
  • a node that contains a cargo object and a reference to a linked list.

    class Node: 
    def __init__(self, cargo=None, next=None):
    self.car = cargo
    self.cdr = next
    def __str__(self):
    return str(self.car)

    def display(lst):
    if lst:
    w("%s " % lst)
    display(lst.cdr)
    else:
    w("nil\n")

Linked List and array

Here is the complete solution;

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next

class Solution:
def __init__(self):
self.head = None

def rev(self, ls):
res = []

self.head = ls
while self.head:
res.append(str(self.head.val))
self.head = self.head.next

return list(reversed(res))

def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
res1 = int(''.join(self.rev(l1)))
res2 = int(''.join(self.rev(l2)))

res3 = str(res1 + res2)
resls = list(reversed([i for i in res3]))

self.head = ListNode(resls[0], None)
finalres = self.head
for i in range(1, len(resls)):
lsn = ListNode(resls[i], None)
finalres.next = lsn
finalres = finalres.next

return self.head

**Explanation**:

I will asume that you know the basics of linked lists i.e, what are they (in case you have confusion please comment).

So in the Solution class, i simply defined a self.head attribute inside its __init__ method which i am going to use to keep track of elements in a linked list. It is initially set to None as right there we don't have any data there.

Then i defined a rev method to reverse the given linked list.

Inside the rev, i created an empty list res to store the data from the linked lists provided.

Rev also takes a linked list as an argument as i will take the data from it and append it to the res list

So i put self.head equal to that linked list ls provided when we call the method.

Then i simply ran a while loop until self.head is defined (i.e, until it is not None which means there is still data).

After every iteration, i kept changing self.head to self.head.next to move forward in the linked list and grab the data from every node of that linked list and append that to res list.

At the end i simply returned the reversed res.

Then i defined another method, addTwoNumbers which takes two linked lists and returns there sum as per the requirement.

First of all i need those two linked lists to be in integer form and reversed ( as per condition). So i used the rev method to reverse them, join method (inbuilt method in python to join a list of strings) to convert the list to string and then int method to convert the string to int.

I did the same with both of the linked lists and stored them in res1 and res2 respectively.

Then i took their sum (res3) and converted it to string as we cannot iterate over an integer .

Then i converted the res3 to a reversed list .

Now the last step, return the whole thing as a listnode.

So i simply created an instance of ListNode;

self.head = ListNode(resls[0], None)

This will create an instance of ListNode with data as first element of resls and next as none.

Then i stored it inside another variable to refrence to the same instance and don't change it.

Then ran a far loop on the remaining elements and kept adding data and next.

Hope you understood. Thanks.

Python - linked list

You should only update the head when you insert at the begining. You were modifying the head when you were appending to the end and printing the linked list.

Here is my modified code:

class Node:
def __init__(self,data):
self.data = data
self.next = None

class LinkedList:
def __init__(self):
self.head = None

def prepend(self,data):
n = Node(data)
if self.head is None:
self.head = n
else:
n.next = self.head
self.head = n

def append(self,data):
n = Node(data)
if self.head is None:
self.head = n
else:
last_node = self.head
while last_node.next:
last_node = last_node.next
last_node.next = n

def get(self):
if self.head:
node_to_print = self.head
while node_to_print.next:
print(node_to_print.data)
node_to_print = node_to_print.next
print(node_to_print.data)

Prints:

1
4
5
6
7

LinkedList implementation in Python not showing beyond the head node

In order to append items to the last Node you need to keep track of the last node.

You also should not override your head pointer in the print function.

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

class LinkedList:
def __init__(self):
self.head = None
self.tail = None

# adding/inserting to the tail
def add(self, val):
node_to_add = ListNode()
node_to_add.val = val
if self.tail == None:
self.head = node_to_add
self.tail = node_to_add
else:
self.tail.next = node_to_add
self.tail = node_to_add

# printing the linked list as a list

def print(self):
list_to_print = []
if not self.head:
return None
current_node = self.head
while current_node:
list_to_print.append(current_node.val)
if current_node.next:
current_node = current_node.next
else:
return list_to_print

Is there a linked list predefined library in Python?

You can also take a look at llist python package, which provides some useful features that deque does not. There are not only doubly linked lists, but also single linked lists data structure in that package. IMHO, one of the biggest advantages of this package is the ability to store a reference to the llist elements.

I don't understand how nodes work in a linked list

Here is a detailed annotation of the code you have supplied. Hopefully this will provide some insight into the things your question is asking about.


The nodes in a linked list look like this, for example:

object:        node1        node2        node3       node4       node5
data type: Node
attributes:
name: data
contents: 'a' 'b' 'c' 'd' 'e'

name: next
contents: node2 node3 node4 node5 None

The linked list object itself looks (in this example) like this:

object:        llist
data type: LinkedList
attributes:
name: head
contents: node1

By convention, the first node of a linked list is known as the head of the linked list, and the last node (namely, the node with a next attribute equal to null, or None in python) is known as the tail of the linked list. In our example, node1 is the head and node5 is the tail.

Let's look at the key methods in your LinkedList class (__iter__, add_after, add_before and remove_node).

The __iter__ method:

    def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next

This method allows us to use language constructs like for node in self to iterate through the nodes in the linked list. In our example:

node = self.head           # assigns `node1` object to variable node

while node is not None: # tests `True`
yield node # makes `node1` available to the caller on call #1
node = node.next # assigns `node2` to variable node

while node is not None: # tests `True`
yield node # makes `node2` available to the caller on call #2
node = node.next # assigns `node3` to variable node

while node is not None: # tests `True`
yield node # makes `node3` available to the caller on call #3
node = node.next # assigns `node4` to variable node

while node is not None: # tests `True`
yield node # makes `node4` available to the caller on call #4
node = node.next # assigns `node5` to variable node

while node is not None: # tests `True`
yield node # makes `node5` available to the caller on call #5
node = node.next # assigns `None` to variable node

while node is not None: # tests `False`

The add_after method:

def add_after(self, target_node_data, new_node):

for node in self:
if node.data == target_node_data:
new_node.next = node.next
node.next = new_node
return

This method finds an existing node whose data attribute matches the target_node_data arguments and inserts argument new_node immediately after (or "downstream" of) the matching node.

Suppose we use it like this for our example:

llist.add_after('c', Node('1'))

Then add_after would do this:

for node in self:                    # assigns `node1` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'a', target_node_data is 'c', so comparison tests False

for node in self: # assigns `node2` object to variable node by calling `__iter__`
if node.data == target_node_data: # node2.data is 'b', target_node_data is 'c', so comparison tests False

for node in self: # assigns `node3` object to variable node by calling `__iter__`
if node.data == target_node_data: # node3.data is 'c', target_node_data is 'c', so comparison tests True

# we now want to "splice" new_node in place between node and node.next
new_node.next = node.next # assigns `node4` object (which is referenced by node.next) to new_node.next
node.next = new_node # update node.next to now reference new_node
# NOTE: further down in this answer, we will refer to the node object we have added here as node3_1

return # the method has finished its work, so it returns without examining any further downstream nodes

The nodes in our linked list example now look like this:

object:        node1        node2        node3        node3_1     node4       node5
data type: Node
attributes:
name: data
contents: 'a' 'b' 'c' '1' 'd' 'e'

name: next
contents: node2 node3 node3_1 node4 node5 None

The add_before method:

    def add_before(self, target_node_data, new_node):

if self.head.data == target_node_data:
return self.add_first(new_node)

for node in self:
if node.data == target_node_data:
prev_node.next = new_node
new_node.next = node
return
prev_node = node

This method finds an existing node whose data attribute matches the target_node_data arguments and inserts argument new_node immediately before (or "upstream" of) the matching node.

Suppose we use it like this for our example:

llist.add_before('d', Node('2'))

Then add_before would do this:

if self.head.data == target_node_data:  # handles an edge case: if head is the node we want to add our node before, we need to update our head attribute
return self.add_first(new_node) # this method is not shown in your question, but would simply do this: new_node.next = self.head; self.head = new_node
# NOTE: does not apply in our example

for node in self: # assigns `node1` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'a', target_node_data is 'd', so comparison tests False
prev_node = node # save a reference to the 'node1' object in variable prev_node

for node in self: # assigns `node2` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'b', target_node_data is 'd', so comparison tests False
prev_node = node # save a reference to the 'node2' object in variable prev_node

for node in self: # assigns `node3` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'c', target_node_data is 'd', so comparison tests False
prev_node = node # save a reference to the 'node3' object in variable prev_node

for node in self: # assigns `node3_1` object to variable node by calling `__iter__`
if node.data == target_node_data: # node3_1.data is '1', target_node_data is 'd', so comparison tests False
prev_node = node # save a reference to the 'node3_1' object in variable prev_node

for node in self: # assigns `node4` object to variable node by calling `__iter__`
if node.data == target_node_data: # node4.data is 'd', target_node_data is 'd', so comparison tests True

# we now want to "splice" new_node in place
prev_node.next = new_node # assigns the object referenced by the new_node argument to the next attribute of 'node3_1'
new_node.next = node # assigns 'node4' to the next attribute of new_node
# NOTE: further down in this answer, we will refer to the node object we have added here as node3_2

return # the method has finished its work, so it returns without examining any further downstream nodes

The nodes in our linked list example now look like this:

object:        node1        node2        node3        node3_1     node3_2     node4       node5
data type: Node
attributes:
name: data
contents: 'a' 'b' 'c' '1' '2' 'd' 'e'

name: next
contents: node2 node3 node3_1 node3_2 node4 node5 None

The remove_node method:

    def remove_node(self, target_node_data):

if self.head.data == target_node_data:
self.head = self.head.next
return

previous_node = self.head
for node in self:
if node.data == target_node_data:
previous_node.next = node.next
return
previous_node = node

This method finds an existing node whose data attribute matches the target_node_data arguments and inserts argument new_node immediately before (or "upstream" of) the matching node.

Suppose we use it like this for our example:

llist.remove_node('c')

Then remove_node would do this:

if self.head.data == target_node_data:  # handles an edge case: if head is the node we want to remove, we need to update our head attribute
self.head = self.head.next # simply assign self.head.next to the attribute self.head
# NOTE: does not apply in our example

previous_node = self.head # save a reference to the 'node1' object in variable previous_node

for node in self: # assigns `node1` object to variable node by calling `__iter__`
if node.data == target_node_data: # node1.data is 'a', target_node_data is 'c', so comparison tests False
previous_node = node # save a reference to the 'node1' object in variable previous_node

for node in self: # assigns `node2` object to variable node by calling `__iter__`
if node.data == target_node_data: # node2.data is 'b', target_node_data is 'c', so comparison tests False
previous_node = node # save a reference to the 'node2' object in variable previous_node

for node in self: # assigns `node3` object to variable node by calling `__iter__`
if node.data == target_node_data: # node3.data is 'c', target_node_data is 'c', so comparison tests True
previous_node.next = node.next # update the next attribute of 'node2' to refer to the next attribute of 'node3', which is 'node3_1'
# NOTE: the object 'node3' is no longer referenced by the next attribute of any nodes in our linked list, which means it has now been removed

return # the method has finished its work, so it returns without examining any further downstream nodes

The nodes in our linked list example now look like this:

object:        node1        node2        node3_1     node3_2     node4       node5
data type: Node
attributes:
name: data
contents: 'a' 'b' '1' '2' 'd' 'e'

name: next
contents: node2 node3_1 node3_2 node4 node5 None

Sort entire Linked List into Ascending order based on String Value - Python

A few issues with your attempt:

  • The algorithm only makes one visit to every node. It is not possible to sort a list in just one sweep. Bubble sort needs two loops (nested). The outer loop keeps looping for as long as the inner loop had to make swaps. Once the inner loop does not find any pair to swap, the list is sorted, and the outer loop can stop.

  • A swap of two adjacent nodes in general needs two references to change. The next attribute of the node that sits before that pair needs to be changed as well, and your code is not doing that.

  • Sorting may mean that that what was originally the head node, no longer sits at the head, and so your code must foresee an assignment to self.head_node... or else the "sorted" version will always start with the same node as before the sort happened.

I would suggest to first create a dummy node that sits before the head node. This helps to simplify the code when the head node needs to be swapped. In that case the dummy's next attribute will change just like any other node's next can change. When all is done, we can then read what is the node that comes after the dummy, and make it the new head node.

    def sort_linked_list(self):
sentinel = ListNode(None)
sentinel.next = self.head_node

dirty = True
while dirty: # Repeat until the inner loop finds nothing to swap
dirty = False
node = sentinel
# keep comparing the pair that follows after(!) `node`
while node.next and node.next.next:
first = node.next
second = first.next
if first.song.song_name > second.song.song_name:
# A swap needs to set two(!) next attributes
node.next = second
first.next = second.next
second.next = first
dirty = True # Indicate that the outer loop needs another iteration
node = node.next

# Make sure the head node references the right node after sorting
self.head_node = sentinel.next

Here is a demo which quickly creates a few nodes with your classes and then runs the above method and finally traverses the sorted list:

# Your code without change, except in the `sort_linked_list` method
class Song:
def __init__(self, song_id, song_name, song_length):
self.song_id = song_id
self.song_name = song_name
self.song_length = song_length

def __str__(self):
return str({'song_id':self.song_id,
'song_name':self.song_name,
'song_length':self.song_length})


class ListNode:
def __init__(self, song:Song):
self.song = song
self.next = None

def __str__(self):
return str(self.song)


class LinkedList:
def __init__(self):
self.head_node = None
self.count = 0

def traversal(self):
if self.head_node is None:
return
temp_node = self.head_node
while(temp_node != None):
print(temp_node.song)
temp_node = temp_node.next
return

def insert_at_start(self, node):
if self.head_node is None:
self.head_node = node
self.count = self.count + 1
return True
node.next = self.head_node
self.head_node = node
return True

def sort_linked_list(self):
sentinel = ListNode(None)
sentinel.next = self.head_node

dirty = True
while dirty: # Repeat until the inner loop finds nothing to swap
dirty = False
node = sentinel
# keep comparing the pair that follows after(!) `node`
while node.next and node.next.next:
first = node.next
second = first.next
if first.song.song_name > second.song.song_name:
# A swap needs to set two(!) next attributes
node.next = second
first.next = second.next
second.next = first
dirty = True # Indicate that the outer loop needs another iteration
node = node.next

# Make sure the head node references the right node after sorting
self.head_node = sentinel.next

# Demo
titles = [
"Smells Like Teen Spirit",
"Billie Jean",
"Stayin’ Alive",
"I Will Survive",
"Whole Lotta Love",
"Sweet Child O’Mine",
"Scream and Shout",
"Santeria",
"Alright",
"Thrift Shop"
]

lst = LinkedList()
for i, title in enumerate(titles):
lst.insert_at_start(ListNode(Song(i, title, len(title))))
lst.sort_linked_list()
lst.traversal() # Outputs the 10 songs in sorted order


Related Topics



Leave a reply



Submit