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
Adding Days to a Date in Python
String Concatenation of Two Pandas Columns
How to Get Monitor Resolution in Python
How to Convert Each Item in the List to String, for the Purpose of Joining Them
How to Get the Logical Xor of Two Variables in Python
Keep Only Date Part When Using Pandas.To_Datetime
How Would You Make a Comma-Separated String from a List of Strings
Pandas: Drop Consecutive Duplicates
Why Python 3.6.1 Throws Attributeerror: Module 'Enum' Has No Attribute 'Intflag'
Is It Pythonic: Naming Lambdas
How to Convert Canvas Content to an Image
How to Convert SQLalchemy Row Object to a Python Dict
What Does 'Weight' Do in Tkinter