I am trying to solve a linked list coding challenge in python. And I have given only following class to create a linked list
# Definition for singly-linked list.
class ListNode[object]:
def __init__[self, x]:
self.val = x
self.next = None
I can create a linked list something like this
x = ListNode[1]
x.next = ListNode[4]
x.next.next = ListNode[5]
however, How do I create iterativly [inside a for loop]
asked May 4, 2019 at 23:14
Gaurang ShahGaurang Shah
10.6k5 gold badges65 silver badges119 bronze badges
You need two "pointers" that memorize the head and the tail of your list. The head is initialized once. You will eventually use it to access the whole list. The tail changes every time you add another node:
data = [5, 1, 7, 96]
tail = head = ListNode[data[0]]
for x in data[1:]:
tail.next = ListNode[x] # Create and add another node
tail = tail.next # Move the tail pointer
answered May 5, 2019 at 3:23
You can do something like:
arr = [1,4,5]
for i in arr:
x = ListNode[i]
x = x.next
But now x will become None
. As there's nothing else to keep track, you can't print the elements.
You can verify this by printing the values of x.val in between the loop:
arr = [1,4,5]
for i in arr:
x = ListNode[i]
print[x.val]
x = x.next
output:
1
4
5
answered May 4, 2019 at 23:21
R4444R4444
1,9281 gold badge16 silver badges27 bronze badges
1
You can add a next
argument to the constructor:
class ListNode[object]:
def __init__[self, x, next=None]:
self.x = x
self.next = next
head = None
for x in [5, 1, 7, 96]:
head = ListNode[x, next=head]
# Linked list looks like:
# [96] -> [ 7] -> [ 1] -> [ 5] -> None
answered May 4, 2019 at 23:40
Brian RodriguezBrian Rodriguez
4,1121 gold badge14 silver badges37 bronze badges
Educative Answers Team
A linked list is a data structure made of a chain of node objects. Each node contains a value and a pointer to the next node in the chain.
Linked lists are preferred over arrays due to their dynamic size and ease of insertion and deletion properties.
The head pointer points to the first
node, and the last element of the list points to null
. When the list is empty, the head pointer points to null
.
Linked lists in Python
Original Python does not ship with a built-in linked list data structure like the one seen in Java.
Let’s see how we can create our own implementation of a standard class-based singly linked list in Python.
1. Start with a single node
Let’s start with a single node since linking several nodes gives us a complete list. For this, we make a Node
class that holds some data
and a single pointer next
, that will be used to point to the next Node
type object in the Linked List.
# A single node of a singly linked list class Node: # constructor def __init__[self, data, next=None]: self.data = data self.next = next # Creating a single node first = Node[3] print[first.data]
2. Join nodes to get a linked list
The next step is to join multiple single nodes containing data
using the next
pointers, and have a single head
pointer pointing to a complete instance of a Linked List.
Using the head
pointer, we will be able to traverse the whole list,
even perform all kinds of list manipulations while we are at it.
For this, we create a LinkedList
class with a single head
pointer:
# A single node of a singly linked list class Node: # constructor def __init__[self, data = None, next=None]: self.data = data self.next = next # A Linked List class with a single head node class LinkedList: def __init__[self]: self.head = None # Linked List with a single node LL = LinkedList[] LL.head = Node[3] print[LL.head.data]
3. Add required methods to the LinkedList
class
Last but not least, we can add various linked list manipulation methods in our implementation.
Let’s have a look at the insertion and print methods for our LinkedList
implementation below:
# A single node of a singly linked list class Node: # constructor def __init__[self, data = None, next=None]: self.data = data self.next = next # A Linked List class with a single head node class LinkedList: def __init__[self]: self.head = None # insertion method for the linked list def insert[self, data]: newNode = Node[data] if[self.head]: current = self.head while[current.next]: current = current.next current.next = newNode else: self.head = newNode # print method for the linked list def printLL[self]: current = self.head while[current]: print[current.data] current = current.next # Singly Linked List with insertion and print methods LL = LinkedList[] LL.insert[3] LL.insert[4] LL.insert[5] LL.printLL[]
RELATED TAGS
data structures
python
linked list
node
classes
Copyright ©2022 Educative, Inc. All rights reserved