Python node class
The nodes are created by implementing a class which will hold the pointers along with the data element. In the below example we create a class named daynames to hold the name of the weekdays. The nextval pointer is initialized to null and three nodes and initialized with values as shown.,The additional operations like insertion and deletion can be done by implementing appropriate methods by using this node containers in the general data structures like linked lists and trees. So we study them in the next chapters.,Nodes are the foundations on which various other data structures linked lists and trees can be handled in python.,We can traverse the elements of the node created above by creating a variable and assigning the first element to it. Then we use a while loop and nextval pointer to print out all the node elements. Note that we have one more additional data element and the nextval pointers are properly arranged to get the output as a days of a week in a proper sequence.
The nextval pointer of node e1 poimts to e3 while the nextval pointer of node e3 points to e2.
class daynames: def __init__(self, dataval=None): self.dataval = dataval self.nextval = None e1 = daynames('Mon') e2 = daynames('Tue') e3 = daynames('Wed') e1.nextval = e3 e3.nextval = e2 We can traverse the elements of the node created above by creating a variable and assigning the first element to it. Then we use a while loop and nextval pointer to print out all the node elements. Note that we have one more additional data element and the nextval pointers are properly arranged to get the output as a days of a week in a proper sequence.
class daynames: def __init__(self, dataval=None): self.dataval = dataval self.nextval = None e1 = daynames('Mon') e2 = daynames('Wed') e3 = daynames('Tue') e4 = daynames('Thu') e1.nextval = e3 e3.nextval = e2 e2.nextval = e4 thisvalue = e1 while thisvalue: print(thisvalue.dataval) thisvalue = thisvalue.nextval When the above code is executed, it produces the following result.
Answer by Eli Miles
Step 2: Creating a Class for a Single-Linked List,Step 1: Node as a Data Structure,Step 6: Creating a Double-Linked List,Step 7: Creating Double-Linked Lists with deque
Listing 1: The ListNode class
class ListNode: def __init__(self, data): "constructor to initiate this object" # store data self.data = data # store reference (next item) self.next = None return def has_value(self, value): "method to compare the value with the node data" if self.data == value: return True else: return False Listing 2: Instantiation of nodes
node1 = ListNode(15) node2 = ListNode(8.2) node3 = ListNode("Berlin") Listing 3: The SingleLinkedList class (part one)
class SingleLinkedList: def __init__(self): "constructor to initiate this object" self.head = None self.tail = None return Listing 4: The SingleLinkedList class (part two)
def add_list_item(self, item): "add an item at the end of the list" if not isinstance(item, ListNode): item = ListNode(item) if self.head is None: self.head = item else: self.tail.next = item self.tail = item return Listing 5: The SingleLinkedList class (part three)
def list_length(self): "returns the number of list items" count = 0 current_node = self.head while current_node is not None: # increase counter by one count = count + 1 # jump to the linked node current_node = current_node.next return count Listing 6: The SingleLinkedList class (part four)
def output_list(self): "outputs the list (the value of the node, actually)" current_node = self.head while current_node is not None: print(current_node.data) # jump to the linked node current_node = current_node.next return Listing 7: Creation of nodes and list output
# create four single nodes node1 = ListNode(15) node2 = ListNode(8.2) item3 = "Berlin" node4 = ListNode(15) track = SingleLinkedList() print("track length: %i" % track.list_length()) for current_item in [node1, node2, item3, node4]: track.add_list_item(current_item) print("track length: %i" % track.list_length()) track.output_list() Listing 8: Adding nodes to the list
$ python3 simple-list.py track length: 0 track length: 1 15 track length: 2 15 8.2 track length: 3 15 8.2 Berlin track length: 4 15 8.2 Berlin 15 Listing 9: The search method unordered_search()
def unordered_search (self, value): "search the linked list for the node that has this value" # define current_node current_node = self.head # define position node_id = 1 # define list of results results = [] while current_node is not None: if current_node.has_value(value): results.append(node_id) # jump to the linked node current_node = current_node.next node_id = node_id + 1 return results Listing 10: Removing a node by node number
def remove_list_item_by_id(self, item_id): "remove the list item with the item id" current_id = 1 current_node = self.head previous_node = None while current_node is not None: if current_id == item_id: # if this is the first node (head) if previous_node is not None: previous_node.next = current_node.next else: self.head = current_node.next # we don't have to look any further return # needed for the next iteration previous_node = current_node current_node = current_node.next current_id = current_id + 1 return Listing 11: Extended list node class
class ListNode: def __init__(self, data): "constructor class to initiate this object" # store data self.data = data # store reference (next item) self.next = None # store reference (previous item) self.previous = None return def has_value(self, value): "method to compare the value with the node data" if self.data == value: return True else: return False Listing 12: A DoubleLinkedList class
class DoubleLinkedList: def __init__(self): "constructor to initiate this object" self.head = None self.tail = None return def list_length(self): "returns the number of list items" count = 0 current_node = self.head while current_node is not None: # increase counter by one count = count + 1 # jump to the linked node current_node = current_node.next return count def output_list(self): "outputs the list (the value of the node, actually)" current_node = self.head while current_node is not None: print(current_node.data) # jump to the linked node current_node = current_node.next return def unordered_search (self, value): "search the linked list for the node that has this value" # define current_node current_node = self.head # define position node_id = 1 # define list of results results = [] while current_node is not None: if current_node.has_value(value): results.append(node_id) # jump to the linked node current_node = current_node.next node_id = node_id + 1 return results def add_list_item(self, item): "add an item at the end of the list" if isinstance(item, ListNode): if self.head is None: self.head = item item.previous = None item.next = None self.tail = item else: self.tail.next = item item.previous = self.tail self.tail = item return Listing 14: Removing an item from a double-linked list
def remove_list_item_by_id(self, item_id): "remove the list item with the item id" current_id = 1 current_node = self.head while current_node is not None: previous_node = current_node.previous next_node = current_node.next if current_id == item_id: # if this is the first node (head) if previous_node is not None: previous_node.next = next_node if next_node is not None: next_node.previous = previous_node else: self.head = next_node if next_node is not None: next_node.previous = None # we don't have to look any further return # needed for the next iteration current_node = next_node current_id = current_id + 1 return Listing 15: Building a double-linked list
# create three single nodes node1 = ListNode(15) node2 = ListNode(8.2) node3 = ListNode("Berlin") node4 = ListNode(15) track = DoubleLinkedList() print("track length: %i" % track.list_length()) for current_node in [node1, node2, node3, node4]: track.add_list_item(current_node) print("track length: %i" % track.list_length()) track.output_list() results = track.unordered_search(15) print(results) track.remove_list_item_by_id(4) track.output_list() Listing 16: ListNode class with deque (simplified)
from collections import deque class ListNode: def __init__(self, data): "constructor class to initiate this object" # store data self.data = data return track = deque([node1, node2, node3]) print("three items (initial list):") for item in track: print(item.data) Listing 18: Adding an element at the beginning of a list
# add an item at the beginning node4 = ListNode(15) track.append_left(node4) print("four items (added as the head):") for item in track: print(item.data) Listing 19: Adding an element at the end of the list
# add an item at the end node5 = ListNode("Moscow") print("five items (added at the end):") track.append(node5) for item in track: print(item.data) Answer by Alma Shaffer
The first line handles the base case by doing nothing. The next two lines split the list into head and tail. The last two lines print the list. The comma at the end of the last line keeps Python from printing a newline after each node.,To make it interesting, we need a list with more than one node:,To traverse a linked list, it is common to use a loop variable like node to refer to each of the nodes in succession.,One nice thing about the LinkedList class is that it provides a natural place to put wrapper functions like print_backward_nicely, which we can make a method of the LinkedList class:
class Node: def __init__(self, cargo=None, next=None): self.cargo = cargo self.next = next def __str__(self): return str(self.cargo) Answer by Wells Kennedy
You need to find the last node without a .nextEl pointer and add the node there:, @user1576208: newNode.nextEl, someNode.nextEl = someNode.nextEl, newNode inserts a node before someNode. – Martijn Pieters ♦ Feb 17 ’13 at 12:20 ,Connect and share knowledge within a single location that is structured and easy to search.,As exercise, I would like to create my own node/list class. Anyway I don’t understand how to add a node to list. here’s my code:
You need to find the last node without a .nextEl pointer and add the node there:
def add(self, newNode): node = self.firstNode while node.nextEl is not None: node = next.nextEl node.nextEl = newNode Because this has to traverse the whole list, most linked-list implementations also keep a reference to the last element:
class List(object): first = last = None def __init__(self, fnode): self.add(fnode) def add(self, newNode): if self.first is None: self.first = self.last = newNode else: self.last.nextEl = self.last = newNode Unless this is Python 3, use new-style classes by inheriting from object :
Answer by Alexis Novak
For this, we create a LinkedList class with a single head pointer:,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.,Let’s see how we can create our own implementation of a standard class-based singly linked list in Python.,Last but not least, we can add various linked list manipulation methods in our implementation.
# 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)Node Class for a Linked List with Object Oriented Python
When you come to study Data Structures such as Stacks, Queues, Linked Lists and Binary Trees for A Level Computer Science, you will often make use of Object Oriented Programming. That is a bit of a double whammy if you are not yet very confident with OOP, and it can seem a bit overwhelming.
I’ve made a video which will help you to get started on both these topics. All of the data structures mentioned above make use of a Node class which has two properties – data and next . The data part can be thought of the “cargo” and is simply the information we wish to store in our node. The next property is a reference to the node we wish our current nose to point to. It is set to None by default. It is by connecting nodes in various ways that we can create the different data structures. Please note that this “linked list based” approach is not the only one that can be used, but it is very common and studying it will serve you well in your exam.
I have provided the code from the video for you convenience. As usual, you should type it into your favourite editor and run it, without copy-pasting. Then change some things, break it, fix it make it your own.
Let me know how you get on in the comments if you wish.
Python listing for a Node Class for A Level Computer Science
class Node: def __init__(self, data): self.data = data self.next = None def print_list(node): current = node while current is not None: print(current.data, end=" ") current = current.next print() node1 = Node("A") print(node1.data) # A -> Ø node2 = Node("B") node3 = Node("C") node1.next = node2 node2.next = node3 print_list(node1) # A -> B -> C -> Ø