CODEWITHSUNDEEP
python-3.xdata-structureslinked-listsingly-linked-list
mateo
mateo

Reputation: 103

Python LinkedList with 2 pointers

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

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

    def insert_node(self, node_data):
        node = Node(node_data)

        if not self.head:
            self.head = node
        else:
            self.tail.next = node


        self.tail = node

# Complete the printLinkedList function below.

    def printList(self):
        while self.head is not None:
            print(self.head.data)
            self.head = self.head.next

l = LinkedList()
l.insert_node(5)
l.insert_node(10)
l.insert_node(19)
l.printList()

I am trying to implement linkedlist using iterative method. I have 2 pointer(head, tail). so is there anyway to avoid using 2 pointers without recursion. and for printList function is is a good practice to use only head pointer. any feedback is appreciated

Upvotes: 3

Views: 1644

Answers (2)

Alexandros Platanios
Alexandros Platanios

Reputation: 1

def getList(self):
    data = []
    currentNode = self.head
    while currentNode is not None:
        data.append( currentNode.data )
        currentNode = currentNode.next
    return data

Upvotes: 0

jhill515
jhill515

Reputation: 943

With your current Linked List implementation, self.tail really isn't serving any purpose other than speading up insertion at the end. You could drop it by having all of your Linked List operations iterate from the head-pointer as you do in your printList() method. Bear in mind, though this does avoid recursion, this inherently forces all operations to be O(n); this isn't bad, though, as this is typical of simplistic Linked Lists.

The purpose of having the tail-pointer and nodes referencing previous-nodes is so that you can also support reverse-traversal. This is a simple optimization, but the improvement only becomes O(n/2) : good enough for short lists, but meaningless in larger lists. Again, that is the learning point of using such a structure over vectorized, ordered, and tree-like data structures.

Upvotes: 1

Related Questions