Linked List implementation in python 3.x

Question

I took this as a challenge and implemented linked list data structure in python

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

class LinkedList:
    def __init__(self, arr=None):
        if arr in [None, []]:
            self.head = None
        else:
            self.arrayToLinked(arr)

    def arrayToLinked(self, arr):
        self.head = Node(arr[0])
        temp = self.head

        for i in range(1, len(arr)):
            temp.next = Node(arr[i])
            temp = temp.next

    def append(self, new_val):
        new_node = Node(new_val)

        if self.head is None:
            self.head = new_node
            return

        last = self.head

        while last.next is not None:
            last = last.next
        last.next = new_node

    def linkedToArray(self):
        arr = []

        temp = self.head

        while temp is not None:
            arr.append(temp.data)
            temp = temp.next

        return arr

    def removeDuplicates(self):
        pass

    def sort(self):
        arr = []

        temp = self.head

        while temp is not None:
            arr.append(temp.data)
            temp = temp.next

        self.arrayToLinked(sorted(arr))

    def index(self, val):
        temp = self.head
        i = 0

        while temp is not None:
            if temp.data == val: return i
            i += 1
        return -1

    def min(self):
        mini = self.head.data
        temp = self.head

        while temp is not None:
            if mini > temp.data:
                mini = temp.data
        return mini

    def max(self):
        maxi = self.head.data
        temp = self.head

        while temp is not None:
            if maxi < temp.data:
                maxi = temp.data
        return maxi

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    @staticmethod
    def insertNode(prev_node, new_val):
        new_node = Node(new_val)
        new_node.next = prev_node.next
        prev_node.next = new_node

    def insertIndex(self, pos, data):
        data = Node(data)
        i = 0

        temp = self.head

        while i < pos:
            if temp is None or temp.next is None:
                return
            temp = temp.next
            i += 1

        dum = temp
        temp = data
        temp.next = dum
        self.head = temp

    def delete(self, key):
        temp = self.head

        if temp is not None and temp.data == key:
            self.head = temp.next
            return

        prev = None

        while temp is not None:
            if temp.data == key:
                break
            prev = temp
            temp = temp.next

        if temp is None:
            return

        prev.next = temp.next

    def deleteIndex(self, pos):
        if self.head is None:
            return

        temp = self.head

        if pos == 0:
            self.head = temp.next
            return

        for i in range(pos - 1):
            temp = temp.next

            if temp is None:
                break

        if temp is None or temp.next is None:
            return

        val = temp.next.next
        temp.next = None
        temp.next = val

    def pop(self, pos):
        if self.head is None:
            return

        temp = self.head

        if pos == 0:
            self.head = temp.next
            return

        for i in range(pos - 1):
            temp = temp.next

            if temp is None:
                break

        if temp is None or temp.next is None:
            return

        val = temp.next.next
        pop_val = temp.next
        temp.next = None
        temp.next = val

        return pop_val

    def count(self, element):
        temp = self.head
        count = 0

        while temp is not None:
            if temp.data == element:
                count += 1
            temp = temp.next
        return count

    def remove(self, element):
        temp = self.head

        while temp is not None:
            if temp.next is not None and temp.next.data == element:
                dum = temp.next.next
                temp.next = None
                temp.next = dum
            temp = temp.next

    def isLoop(self):
        s = set()
        temp = self.head

        while temp:
            if temp in s:
                return True
            s.add(temp)
            temp = temp.next
        return False

    def findLoop(self):
        s = set()
        temp = self.head

        while temp:
            if temp in s:
                return temp
            s.add(temp)
            temp = temp.next

    def createLoop(self, data):
        ind = self.index(data)

        last = self.head

        while last.next is not None:
            last = last.next

        last.next = self[ind]

    def reverse(self):
        result = None

        temp = self.head

        while temp:
            result = Node(temp.data, temp)
            temp = temp.next

        self.head = result

    def len(self):
        c = 0
        temp = self.head

        while temp is not None:
            c += 1
            temp = temp.next

        return c

    def clear(self):
        self.head = None

    def copy(self):
        return self.arrayToLinked(self.linkedToArray())

    def __getitem__(self, index):
        arr = []
        temp = self.head

        while temp is not None:
            arr.append(temp)
            temp = temp.next

        return arr[index]

    def getValues(self, index):
        arr = []
        temp = self.head

        while temp is not None:
            arr.append(temp.data)
            temp = temp.next

        return arr[index]

    def print(self):
        arr = []
        m = self.head

        while m is not None:
            arr.append(str(m.data))
            m = m.next

        print(' -> '.join(arr))

I want to make the code as short as possible, while maintaining neatness.

Thanks!

Answer 1

This code is pretty neat. One major improvement would be the addition of some magic methods, like __iter__, __getitem__, __setitem__ and __str__.

iter

The magic method you'll use the most wil be __iter__. It will allow you to do for node in linked_list

def __iter__(self):
    current = self.head
    while current:
        yield current
        current = current.next

If there is the possibility for loops in the linked list, this will go on forever. In that case, it might be best to raise a specific exception

class LoopListError(Exception): pass
...
def __iter__(self):
    current = self.head
    visited = set()
    while current:
        if current in visited:
            raise LoopListError("f{current} is part of a loop")
        set.add(current)
        yield current
        current = current.next

Make sure never to change the list while iterating over it. This might lead to strange errors.

__len__

len(self) can be renamed to __len_, so you can do len(linked_list) . It can also be implemented like this:

def __len__(self):
    return sum(1 for _ in self)

If there is a loop in the list, this wil raise the LoopListError. If, in that case, you want the length of the non-looped part of the list, then you can do:

def __len__(self):
    count = 0
    try:
        for _ in self:
            count += 1
    except LoopListError:
        pass
    return count

If you want it to iterate over the nodes values instead of the nodes themselves, you can just change the yield current to yield current.data. Whichever option is best depends on the design of the rest and the use of this list.

I think it's cleaner to provide a separate iter_values method:

def iter_values(self):
    return (node.data for node in self)

You don't need a specific min and max method any more, but can use the builtins

__getitem__

In your implementation, you load the complete linked list into a builtin list. This is not needed. You can use enumerate to loop over the elements, and keep track of the index

def __getitem__(self, index):
    for i, node in enumerate(self):
        if i == index:
            return node
    raise IndexError(f"{index} not found")

This works for positive indices. If you also want to accept negative indices, you need to convert the negative index to a positive one:

def __getitem__(self, index):
    if index < 0:
        l = len(self)
        if abs(index) > l:
            raise IndexError(f"{index} out of range")
        index = l - index

    for i, node in enumerate(self):
        if i == index:
            return node
    raise IndexError(f"{index} out of range")

__bool__

In python, by convention, empty containers are falsey. Their __bool__ function returns False.

def __bool__(self):
    return self.head is not None

arrayToLinked

In python, it's seldomly necessary to loop over an index. Instead of for i in range(1, len(arr)), you can use for value in arr:. This only needs a bit of special handling for the head of the list.

Your arrayToLinked method corresponds to list.extend(iterable) on an ordinary list. I only clears the list first. My suggestion would be to skip the clearing of the list. If the user wants a fresh list, he can either explicitly clear it himself, or call the constructor while providing the iterable:

def extend(self, iterable):
    it = iter(iterable)
    if not self:
        try:
            self.head = Node(next(it))
        except StopIteration:
            self.head = None

    for value in it:
        self.append(Node(value))

def __init__(self, iterable=None):
    self.head = None
    if iterable is not None:
        self.extend(iterable)

---

As409_conflict noted in the comments, this might not be the most performant method to use

if you provide a tail method,

def tail(self):
    """
    returns the last element in the linked list. 
    """

    if self.head is None:
        return None
    for current in self:
        pass
    return current


def extend(self, iterable):
    it = iter(iterable)
    if not self:
        try:
            self.head = Node(next(it))
        except StopIteration:
            return
    current = self.tail()

    for value in it:
        current.next = current = Node(value)

copy

The copy then becomes as simple as

def copy(self):
    return type(self)(self.iter_values())

sort

def sort(self):
    sorted_values = sorted(self.iter_values())
    self.clear()
    self.extend(sorted_values )

Or, If you want to return a new instance

def sort(self):
    return type(self)(sorted(self.iter_values()))

---

In general, I suggest you take a look at the Python data model, and what methods a standard list provides, and thy to mimic those behaviours