What's the easiest way to use a linked list in python? In scheme, a linked list is defined simply by '(1 2 3 4 5). Python's lists, [1, 2, 3, 4, 5], and tuples, (1, 2, 3, 4, 5), are not, in fact, linked lists, and linked lists have some nice properties such as constant-time concatenation, and being able to reference separate parts of them. Make them immutable and they are really easy to work with!
Python Linked List
Viewed 331891
29 Answers
For some needs, a deque may also be useful. You can add and remove items on both ends of a deque at O(1) cost.
from collections import deque
d = deque([1,2,3,4])
print d
for x in d:
print x
print d.pop(), d
I wrote this up the other day
#! /usr/bin/env python
class Node(object):
def __init__(self):
self.data = None # contains the data
self.next = None # contains the reference to the next node
class LinkedList:
def __init__(self):
self.cur_node = None
def add_node(self, data):
new_node = Node() # create a new node
new_node.data = data
new_node.next = self.cur_node # link the new node to the 'previous' node.
self.cur_node = new_node # set the current node to the new one.
def list_print(self):
node = self.cur_node # cant point to ll!
while node:
print node.data
node = node.next
ll = LinkedList()
ll.add_node(1)
ll.add_node(2)
ll.add_node(3)
ll.list_print()
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")
Immutable lists are best represented through two-tuples, with None representing NIL. To allow simple formulation of such lists, you can use this function:
def mklist(*args):
result = None
for element in reversed(args):
result = (element, result)
return result
To work with such lists, I'd rather provide the whole collection of LISP functions (i.e. first, second, nth, etc), than introducing methods.
Here's a slightly more complex version of a linked list class, with a similar interface to python's sequence types (ie. supports indexing, slicing, concatenation with arbitrary sequences etc). It should have O(1) prepend, doesn't copy data unless it needs to and can be used pretty interchangably with tuples.
It won't be as space or time efficient as lisp cons cells, as python classes are obviously a bit more heavyweight (You could improve things slightly with "__slots__ = '_head','_tail'" to reduce memory usage). It will have the desired big O performance characteristics however.
Example of usage:
>>> l = LinkedList([1,2,3,4])
>>> l
LinkedList([1, 2, 3, 4])
>>> l.head, l.tail
(1, LinkedList([2, 3, 4]))
# Prepending is O(1) and can be done with:
LinkedList.cons(0, l)
LinkedList([0, 1, 2, 3, 4])
# Or prepending arbitrary sequences (Still no copy of l performed):
[-1,0] + l
LinkedList([-1, 0, 1, 2, 3, 4])
# Normal list indexing and slice operations can be performed.
# Again, no copy is made unless needed.
>>> l[1], l[-1], l[2:]
(2, 4, LinkedList([3, 4]))
>>> assert l[2:] is l.next.next
# For cases where the slice stops before the end, or uses a
# non-contiguous range, we do need to create a copy. However
# this should be transparent to the user.
>>> LinkedList(range(100))[-10::2]
LinkedList([90, 92, 94, 96, 98])
Implementation:
import itertools
class LinkedList(object):
"""Immutable linked list class."""
def __new__(cls, l=[]):
if isinstance(l, LinkedList): return l # Immutable, so no copy needed.
i = iter(l)
try:
head = i.next()
except StopIteration:
return cls.EmptyList # Return empty list singleton.
tail = LinkedList(i)
obj = super(LinkedList, cls).__new__(cls)
obj._head = head
obj._tail = tail
return obj
@classmethod
def cons(cls, head, tail):
ll = cls([head])
if not isinstance(tail, cls):
tail = cls(tail)
ll._tail = tail
return ll
# head and tail are not modifiable
@property
def head(self): return self._head
@property
def tail(self): return self._tail
def __nonzero__(self): return True
def __len__(self):
return sum(1 for _ in self)
def __add__(self, other):
other = LinkedList(other)
if not self: return other # () + l = l
start=l = LinkedList(iter(self)) # Create copy, as we'll mutate
while l:
if not l._tail: # Last element?
l._tail = other
break
l = l._tail
return start
def __radd__(self, other):
return LinkedList(other) + self
def __iter__(self):
x=self
while x:
yield x.head
x=x.tail
def __getitem__(self, idx):
"""Get item at specified index"""
if isinstance(idx, slice):
# Special case: Avoid constructing a new list, or performing O(n) length
# calculation for slices like l[3:]. Since we're immutable, just return
# the appropriate node. This becomes O(start) rather than O(n).
# We can't do this for more complicated slices however (eg [l:4]
start = idx.start or 0
if (start >= 0) and (idx.stop is None) and (idx.step is None or idx.step == 1):
no_copy_needed=True
else:
length = len(self) # Need to calc length.
start, stop, step = idx.indices(length)
no_copy_needed = (stop == length) and (step == 1)
if no_copy_needed:
l = self
for i in range(start):
if not l: break # End of list.
l=l.tail
return l
else:
# We need to construct a new list.
if step < 1: # Need to instantiate list to deal with -ve step
return LinkedList(list(self)[start:stop:step])
else:
return LinkedList(itertools.islice(iter(self), start, stop, step))
else:
# Non-slice index.
if idx < 0: idx = len(self)+idx
if not self: raise IndexError("list index out of range")
if idx == 0: return self.head
return self.tail[idx-1]
def __mul__(self, n):
if n <= 0: return Nil
l=self
for i in range(n-1): l += self
return l
def __rmul__(self, n): return self * n
# Ideally we should compute the has ourselves rather than construct
# a temporary tuple as below. I haven't impemented this here
def __hash__(self): return hash(tuple(self))
def __eq__(self, other): return self._cmp(other) == 0
def __ne__(self, other): return not self == other
def __lt__(self, other): return self._cmp(other) < 0
def __gt__(self, other): return self._cmp(other) > 0
def __le__(self, other): return self._cmp(other) <= 0
def __ge__(self, other): return self._cmp(other) >= 0
def _cmp(self, other):
"""Acts as cmp(): -1 for self<other, 0 for equal, 1 for greater"""
if not isinstance(other, LinkedList):
return cmp(LinkedList,type(other)) # Arbitrary ordering.
A, B = iter(self), iter(other)
for a,b in itertools.izip(A,B):
if a<b: return -1
elif a > b: return 1
try:
A.next()
return 1 # a has more items.
except StopIteration: pass
try:
B.next()
return -1 # b has more items.
except StopIteration: pass
return 0 # Lists are equal
def __repr__(self):
return "LinkedList([%s])" % ', '.join(map(repr,self))
class EmptyList(LinkedList):
"""A singleton representing an empty list."""
def __new__(cls):
return object.__new__(cls)
def __iter__(self): return iter([])
def __nonzero__(self): return False
@property
def head(self): raise IndexError("End of list")
@property
def tail(self): raise IndexError("End of list")
# Create EmptyList singleton
LinkedList.EmptyList = EmptyList()
del EmptyList
When using immutable linked lists, consider using Python's tuple directly.
ls = (1, 2, 3, 4, 5)
def first(ls): return ls[0]
def rest(ls): return ls[1:]
Its really that ease, and you get to keep the additional funcitons like len(ls), x in ls, etc.
class LinkedStack:
'''LIFO Stack implementation using a singly linked list for storage.'''
_ToList = []
#---------- nested _Node class -----------------------------
class _Node:
'''Lightweight, nonpublic class for storing a singly linked node.'''
__slots__ = '_element', '_next' #streamline memory usage
def __init__(self, element, next):
self._element = element
self._next = next
#--------------- stack methods ---------------------------------
def __init__(self):
'''Create an empty stack.'''
self._head = None
self._size = 0
def __len__(self):
'''Return the number of elements in the stack.'''
return self._size
def IsEmpty(self):
'''Return True if the stack is empty'''
return self._size == 0
def Push(self,e):
'''Add element e to the top of the Stack.'''
self._head = self._Node(e, self._head) #create and link a new node
self._size +=1
self._ToList.append(e)
def Top(self):
'''Return (but do not remove) the element at the top of the stack.
Raise exception if the stack is empty
'''
if self.IsEmpty():
raise Exception('Stack is empty')
return self._head._element #top of stack is at head of list
def Pop(self):
'''Remove and return the element from the top of the stack (i.e. LIFO).
Raise exception if the stack is empty
'''
if self.IsEmpty():
raise Exception('Stack is empty')
answer = self._head._element
self._head = self._head._next #bypass the former top node
self._size -=1
self._ToList.remove(answer)
return answer
def Count(self):
'''Return how many nodes the stack has'''
return self.__len__()
def Clear(self):
'''Delete all nodes'''
for i in range(self.Count()):
self.Pop()
def ToList(self):
return self._ToList
I did also write a Single Linked List based on some tutorial, which has the basic two Node and Linked List classes, and some additional methods for insertion, delete, reverse, sorting, and such.
It's not the best or easiest, works OK though.
"""
Single Linked List (SLL):
A simple object-oriented implementation of Single Linked List (SLL)
with some associated methods, such as create list, count nodes, delete nodes, and such.
"""
class Node:
"""
Instantiates a node
"""
def __init__(self, value):
"""
Node class constructor which sets the value and link of the node
"""
self.info = value
self.link = None
class SingleLinkedList:
"""
Instantiates the SLL class
"""
def __init__(self):
"""
SLL class constructor which sets the value and link of the node
"""
self.start = None
def create_single_linked_list(self):
"""
Reads values from stdin and appends them to this list and creates a SLL with integer nodes
"""
try:
number_of_nodes = int(input(" Enter a positive integer between 1-50 for the number of nodes you wish to have in the list: "))
if number_of_nodes <= 0 or number_of_nodes > 51:
print(" The number of nodes though must be an integer between 1 to 50!")
self.create_single_linked_list()
except Exception as e:
print(" Error: ", e)
self.create_single_linked_list()
try:
for _ in range(number_of_nodes):
try:
data = int(input(" Enter an integer for the node to be inserted: "))
self.insert_node_at_end(data)
except Exception as e:
print(" Error: ", e)
except Exception as e:
print(" Error: ", e)
def count_sll_nodes(self):
"""
Counts the nodes of the linked list
"""
try:
p = self.start
n = 0
while p is not None:
n += 1
p = p.link
if n >= 1:
print(f" The number of nodes in the linked list is {n}")
else:
print(f" The SLL does not have a node!")
except Exception as e:
print(" Error: ", e)
def search_sll_nodes(self, x):
"""
Searches the x integer in the linked list
"""
try:
position = 1
p = self.start
while p is not None:
if p.info == x:
print(f" YAAAY! We found {x} at position {position}")
return True
#Increment the position
position += 1
#Assign the next node to the current node
p = p.link
else:
print(f" Sorry! We couldn't find {x} at any position. Maybe, you might want to use option 9 and try again later!")
return False
except Exception as e:
print(" Error: ", e)
def display_sll(self):
"""
Displays the list
"""
try:
if self.start is None:
print(" Single linked list is empty!")
return
display_sll = " Single linked list nodes are: "
p = self.start
while p is not None:
display_sll += str(p.info) + "\t"
p = p.link
print(display_sll)
except Exception as e:
print(" Error: ", e)
def insert_node_in_beginning(self, data):
"""
Inserts an integer in the beginning of the linked list
"""
try:
temp = Node(data)
temp.link = self.start
self.start = temp
except Exception as e:
print(" Error: ", e)
def insert_node_at_end(self, data):
"""
Inserts an integer at the end of the linked list
"""
try:
temp = Node(data)
if self.start is None:
self.start = temp
return
p = self.start
while p.link is not None:
p = p.link
p.link = temp
except Exception as e:
print(" Error: ", e)
def insert_node_after_another(self, data, x):
"""
Inserts an integer after the x node
"""
try:
p = self.start
while p is not None:
if p.info == x:
break
p = p.link
if p is None:
print(f" Sorry! {x} is not in the list.")
else:
temp = Node(data)
temp.link = p.link
p.link = temp
except Exception as e:
print(" Error: ", e)
def insert_node_before_another(self, data, x):
"""
Inserts an integer before the x node
"""
try:
# If list is empty
if self.start is None:
print(" Sorry! The list is empty.")
return
# If x is the first node, and new node should be inserted before the first node
if x == self.start.info:
temp = Node(data)
temp.link = p.link
p.link = temp
# Finding the reference to the prior node containing x
p = self.start
while p.link is not None:
if p.link.info == x:
break
p = p.link
if p.link is not None:
print(f" Sorry! {x} is not in the list.")
else:
temp = Node(data)
temp.link = p.link
p.link = temp
except Exception as e:
print(" Error: ", e)
def insert_node_at_position(self, data, k):
"""
Inserts an integer in k position of the linked list
"""
try:
# if we wish to insert at the first node
if k == 1:
temp = Node(data)
temp.link = self.start
self.start = temp
return
p = self.start
i = 1
while i < k-1 and p is not None:
p = p.link
i += 1
if p is None:
print(f" The max position is {i}")
else:
temp = Node(data)
temp.link = self.start
self.start = temp
except Exception as e:
print(" Error: ", e)
def delete_a_node(self, x):
"""
Deletes a node of a linked list
"""
try:
# If list is empty
if self.start is None:
print(" Sorry! The list is empty.")
return
# If there is only one node
if self.start.info == x:
self.start = self.start.link
# If more than one node exists
p = self.start
while p.link is not None:
if p.link.info == x:
break
p = p.link
if p.link is None:
print(f" Sorry! {x} is not in the list.")
else:
p.link = p.link.link
except Exception as e:
print(" Error: ", e)
def delete_sll_first_node(self):
"""
Deletes the first node of a linked list
"""
try:
if self.start is None:
return
self.start = self.start.link
except Exception as e:
print(" Error: ", e)
def delete_sll_last_node(self):
"""
Deletes the last node of a linked list
"""
try:
# If the list is empty
if self.start is None:
return
# If there is only one node
if self.start.link is None:
self.start = None
return
# If there is more than one node
p = self.start
# Increment until we find the node prior to the last node
while p.link.link is not None:
p = p.link
p.link = None
except Exception as e:
print(" Error: ", e)
def reverse_sll(self):
"""
Reverses the linked list
"""
try:
prev = None
p = self.start
while p is not None:
next = p.link
p.link = prev
prev = p
p = next
self.start = prev
except Exception as e:
print(" Error: ", e)
def bubble_sort_sll_nodes_data(self):
"""
Bubble sorts the linked list on integer values
"""
try:
# If the list is empty or there is only one node
if self.start is None or self.start.link is None:
print(" The list has no or only one node and sorting is not required.")
end = None
while end != self.start.link:
p = self.start
while p.link != end:
q = p.link
if p.info > q.info:
p.info, q.info = q.info, p.info
p = p.link
end = p
except Exception as e:
print(" Error: ", e)
def bubble_sort_sll(self):
"""
Bubble sorts the linked list
"""
try:
# If the list is empty or there is only one node
if self.start is None or self.start.link is None:
print(" The list has no or only one node and sorting is not required.")
end = None
while end != self.start.link:
r = p = self.start
while p.link != end:
q = p.link
if p.info > q.info:
p.link = q.link
q.link = p
if p != self.start:
r.link = q.link
else:
self.start = q
p, q = q, p
r = p
p = p.link
end = p
except Exception as e:
print(" Error: ", e)
def sll_has_cycle(self):
"""
Tests the list for cycles using Tortoise and Hare Algorithm (Floyd's cycle detection algorithm)
"""
try:
if self.find_sll_cycle() is None:
return False
else:
return True
except Exception as e:
print(" Error: ", e)
def find_sll_cycle(self):
"""
Finds cycles in the list, if any
"""
try:
# If there is one node or none, there is no cycle
if self.start is None or self.start.link is None:
return None
# Otherwise,
slowR = self.start
fastR = self.start
while slowR is not None and fastR is not None:
slowR = slowR.link
fastR = fastR.link.link
if slowR == fastR:
return slowR
return None
except Exception as e:
print(" Error: ", e)
def remove_cycle_from_sll(self):
"""
Removes the cycles
"""
try:
c = self.find_sll_cycle()
# If there is no cycle
if c is None:
return
print(f" There is a cycle at node: ", c.info)
p = c
q = c
len_cycles = 0
while True:
len_cycles += 1
q = q.link
if p == q:
break
print(f" The cycle length is {len_cycles}")
len_rem_list = 0
p = self.start
while p != q:
len_rem_list += 1
p = p.link
q = q.link
print(f" The number of nodes not included in the cycle is {len_rem_list}")
length_list = len_rem_list + len_cycles
print(f" The SLL length is {length_list}")
# This for loop goes to the end of the SLL, and set the last node to None and the cycle is removed.
p = self.start
for _ in range(length_list-1):
p = p.link
p.link = None
except Exception as e:
print(" Error: ", e)
def insert_cycle_in_sll(self, x):
"""
Inserts a cycle at a node that contains x
"""
try:
if self.start is None:
return False
p = self.start
px = None
prev = None
while p is not None:
if p.info == x:
px = p
prev = p
p = p.link
if px is not None:
prev.link = px
else:
print(f" Sorry! {x} is not in the list.")
except Exception as e:
print(" Error: ", e)
def merge_using_new_list(self, list2):
"""
Merges two already sorted SLLs by creating new lists
"""
merge_list = SingleLinkedList()
merge_list.start = self._merge_using_new_list(self.start, list2.start)
return merge_list
def _merge_using_new_list(self, p1, p2):
"""
Private method of merge_using_new_list
"""
if p1.info <= p2.info:
Start_merge = Node(p1.info)
p1 = p1.link
else:
Start_merge = Node(p2.info)
p2 = p2.link
pM = Start_merge
while p1 is not None and p2 is not None:
if p1.info <= p2.info:
pM.link = Node(p1.info)
p1 = p1.link
else:
pM.link = Node(p2.info)
p2 = p2.link
pM = pM.link
#If the second list is finished, yet the first list has some nodes
while p1 is not None:
pM.link = Node(p1.info)
p1 = p1.link
pM = pM.link
#If the second list is finished, yet the first list has some nodes
while p2 is not None:
pM.link = Node(p2.info)
p2 = p2.link
pM = pM.link
return Start_merge
def merge_inplace(self, list2):
"""
Merges two already sorted SLLs in place in O(1) of space
"""
merge_list = SingleLinkedList()
merge_list.start = self._merge_inplace(self.start, list2.start)
return merge_list
def _merge_inplace(self, p1, p2):
"""
Merges two already sorted SLLs in place in O(1) of space
"""
if p1.info <= p2.info:
Start_merge = p1
p1 = p1.link
else:
Start_merge = p2
p2 = p2.link
pM = Start_merge
while p1 is not None and p2 is not None:
if p1.info <= p2.info:
pM.link = p1
pM = pM.link
p1 = p1.link
else:
pM.link = p2
pM = pM.link
p2 = p2.link
if p1 is None:
pM.link = p2
else:
pM.link = p1
return Start_merge
def merge_sort_sll(self):
"""
Sorts the linked list using merge sort algorithm
"""
self.start = self._merge_sort_recursive(self.start)
def _merge_sort_recursive(self, list_start):
"""
Recursively calls the merge sort algorithm for two divided lists
"""
# If the list is empty or has only one node
if list_start is None or list_start.link is None:
return list_start
# If the list has two nodes or more
start_one = list_start
start_two = self._divide_list(self_start)
start_one = self._merge_sort_recursive(start_one)
start_two = self._merge_sort_recursive(start_two)
start_merge = self._merge_inplace(start_one, start_two)
return start_merge
def _divide_list(self, p):
"""
Divides the linked list into two almost equally sized lists
"""
# Refers to the third nodes of the list
q = p.link.link
while q is not None and p is not None:
# Increments p one node at the time
p = p.link
# Increments q two nodes at the time
q = q.link.link
start_two = p.link
p.link = None
return start_two
def concat_second_list_to_sll(self, list2):
"""
Concatenates another SLL to an existing SLL
"""
# If the second SLL has no node
if list2.start is None:
return
# If the original SLL has no node
if self.start is None:
self.start = list2.start
return
# Otherwise traverse the original SLL
p = self.start
while p.link is not None:
p = p.link
# Link the last node to the first node of the second SLL
p.link = list2.start
def test_merge_using_new_list_and_inplace(self):
"""
"""
LIST_ONE = SingleLinkedList()
LIST_TWO = SingleLinkedList()
LIST_ONE.create_single_linked_list()
LIST_TWO.create_single_linked_list()
print("1️⃣ The unsorted first list is: ")
LIST_ONE.display_sll()
print("2️⃣ The unsorted second list is: ")
LIST_TWO.display_sll()
LIST_ONE.bubble_sort_sll_nodes_data()
LIST_TWO.bubble_sort_sll_nodes_data()
print("1️⃣ The sorted first list is: ")
LIST_ONE.display_sll()
print("2️⃣ The sorted second list is: ")
LIST_TWO.display_sll()
LIST_THREE = LIST_ONE.merge_using_new_list(LIST_TWO)
print("The merged list by creating a new list is: ")
LIST_THREE.display_sll()
LIST_FOUR = LIST_ONE.merge_inplace(LIST_TWO)
print("The in-place merged list is: ")
LIST_FOUR.display_sll()
def test_all_methods(self):
"""
Tests all methods of the SLL class
"""
OPTIONS_HELP = """
Select a method from 1-19:
ℹ️ (1) Create a single liked list (SLL).
ℹ️ (2) Display the SLL.
ℹ️ (3) Count the nodes of SLL.
ℹ️ (4) Search the SLL.
ℹ️ (5) Insert a node at the beginning of the SLL.
ℹ️ (6) Insert a node at the end of the SLL.
ℹ️ (7) Insert a node after a specified node of the SLL.
ℹ️ (8) Insert a node before a specified node of the SLL.
ℹ️ (9) Delete the first node of SLL.
ℹ️ (10) Delete the last node of the SLL.
ℹ️ (11) Delete a node you wish to remove.
ℹ️ (12) Reverse the SLL.
ℹ️ (13) Bubble sort the SLL by only exchanging the integer values.
ℹ️ (14) Bubble sort the SLL by exchanging links.
ℹ️ (15) Merge sort the SLL.
ℹ️ (16) Insert a cycle in the SLL.
ℹ️ (17) Detect if the SLL has a cycle.
ℹ️ (18) Remove cycle in the SLL.
ℹ️ (19) Test merging two bubble-sorted SLLs.
ℹ️ (20) Concatenate a second list to the SLL.
ℹ️ (21) Exit.
"""
self.create_single_linked_list()
while True:
print(OPTIONS_HELP)
UI_OPTION = int(input(" Enter an integer for the method you wish to run using the above help: "))
if UI_OPTION == 1:
data = int(input(" Enter an integer to be inserted at the end of the list: "))
x = int(input(" Enter an integer to be inserted after that: "))
self.insert_node_after_another(data, x)
elif UI_OPTION == 2:
self.display_sll()
elif UI_OPTION == 3:
self.count_sll_nodes()
elif UI_OPTION == 4:
data = int(input(" Enter an integer to be searched: "))
self.search_sll_nodes(data)
elif UI_OPTION == 5:
data = int(input(" Enter an integer to be inserted at the beginning: "))
self.insert_node_in_beginning(data)
elif UI_OPTION == 6:
data = int(input(" Enter an integer to be inserted at the end: "))
self.insert_node_at_end(data)
elif UI_OPTION == 7:
data = int(input(" Enter an integer to be inserted: "))
x = int(input(" Enter an integer to be inserted before that: "))
self.insert_node_before_another(data, x)
elif UI_OPTION == 8:
data = int(input(" Enter an integer for the node to be inserted: "))
k = int(input(" Enter an integer for the position at which you wish to insert the node: "))
self.insert_node_before_another(data, k)
elif UI_OPTION == 9:
self.delete_sll_first_node()
elif UI_OPTION == 10:
self.delete_sll_last_node()
elif UI_OPTION == 11:
data = int(input(" Enter an integer for the node you wish to remove: "))
self.delete_a_node(data)
elif UI_OPTION == 12:
self.reverse_sll()
elif UI_OPTION == 13:
self.bubble_sort_sll_nodes_data()
elif UI_OPTION == 14:
self.bubble_sort_sll()
elif UI_OPTION == 15:
self.merge_sort_sll()
elif UI_OPTION == 16:
data = int(input(" Enter an integer at which a cycle has to be formed: "))
self.insert_cycle_in_sll(data)
elif UI_OPTION == 17:
if self.sll_has_cycle():
print(" The linked list has a cycle. ")
else:
print(" YAAAY! The linked list does not have a cycle. ")
elif UI_OPTION == 18:
self.remove_cycle_from_sll()
elif UI_OPTION == 19:
self.test_merge_using_new_list_and_inplace()
elif UI_OPTION == 20:
list2 = self.create_single_linked_list()
self.concat_second_list_to_sll(list2)
elif UI_OPTION == 21:
break
else:
print(" Option must be an integer, between 1 to 21.")
print()
if __name__ == '__main__':
# Instantiates a new SLL object
SLL_OBJECT = SingleLinkedList()
SLL_OBJECT.test_all_methods()
Expanding Nick Stinemates's answer
class Node(object):
def __init__(self):
self.data = None
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def prepend_node(self, data):
new_node = Node()
new_node.data = data
new_node.next = self.head
self.head = new_node
def append_node(self, data):
new_node = Node()
new_node.data = data
current = self.head
while current.next:
current = current.next
current.next = new_node
def reverse(self):
""" In-place reversal, modifies exiting list"""
previous = None
current_node = self.head
while current_node:
temp = current_node.next
current_node.next = previous
previous = current_node
current_node = temp
self.head = previous
def search(self, data):
current_node = self.head
try:
while current_node.data != data:
current_node = current_node.next
return True
except:
return False
def display(self):
if self.head is None:
print("Linked list is empty")
else:
current_node = self.head
while current_node:
print(current_node.data)
current_node = current_node.next
def list_length(self):
list_length = 0
current_node = self.head
while current_node:
list_length += 1
current_node = current_node.next
return list_length
def main():
linked_list = LinkedList()
linked_list.prepend_node(1)
linked_list.prepend_node(2)
linked_list.prepend_node(3)
linked_list.append_node(24)
linked_list.append_node(25)
linked_list.display()
linked_list.reverse()
linked_list.display()
print(linked_list.search(1))
linked_list.reverse()
linked_list.display()
print("Lenght of singly linked list is: " + str(linked_list.list_length()))
if __name__ == "__main__":
main()
my double Linked List might be understandable to noobies. If you are familiar with DS in C, this is quite readable.
# LinkedList..
class node:
def __init__(self): ##Cluster of Nodes' properties
self.data=None
self.next=None
self.prev=None
class linkedList():
def __init__(self):
self.t = node() // for future use
self.cur_node = node() // current node
self.start=node()
def add(self,data): // appending the LL
self.new_node = node()
self.new_node.data=data
if self.cur_node.data is None:
self.start=self.new_node //For the 1st node only
self.cur_node.next=self.new_node
self.new_node.prev=self.cur_node
self.cur_node=self.new_node
def backward_display(self): //Displays LL backwards
self.t=self.cur_node
while self.t.data is not None:
print(self.t.data)
self.t=self.t.prev
def forward_display(self): //Displays LL Forward
self.t=self.start
while self.t.data is not None:
print(self.t.data)
self.t=self.t.next
if self.t.next is None:
print(self.t.data)
break
def main(self): //This is kind of the main
function in C
ch=0
while ch is not 4: //Switch-case in C
ch=int(input("Enter your choice:"))
if ch is 1:
data=int(input("Enter data to be added:"))
ll.add(data)
ll.main()
elif ch is 2:
ll.forward_display()
ll.main()
elif ch is 3:
ll.backward_display()
ll.main()
else:
print("Program ends!!")
return
ll=linkedList()
ll.main()
Though many more simplifications can be added to this code, I thought a raw implementation would me more grabbable.
Current Implementation of Linked List in Python requires for creation of a separate class, called Node, so that they can be connected using a main Linked List class. In the provided implementation, the Linked List is created without defining a separate class for a node. Using the proposed implementation, Linked Lists are easier to understand and can be simply visualized using the print function.
class Linkedlist:
def __init__(self):
self.outer = None
def add_outermost(self, dt):
self.outer = [dt, self.outer]
def add_innermost(self, dt):
p = self.outer
if not p:
self.outer = [dt, None]
return
while p[1]:
p = p[1]
p[1] = [dt, None]
def visualize(self):
p = self.outer
l = 'Linkedlist: '
while p:
l += (str(p[0])+'->')
p = p[1]
print(l + 'None')
ll = Linkedlist()
ll.add_innermost(8)
ll.add_outermost(3)
ll.add_outermost(5)
ll.add_outermost(2)
ll.add_innermost(7)
print(ll.outer)
ll.visualize()
Related