Implement LinkedList class in python

Question

I am currently study the basic data structure and trying to implement everything as I go. can anyone give me some feedback about class LinkedList how to make the code more elegant. any review are appreciated.

class Node(object):
    def __init__(self, data, n=None):
        self.val = data
        self.next = n

    def get(self):
        return self.data

    def set(self, data):
        self.val = data

    def get_next_node(self):
        return self.next

    def set_next_node(self, data):
        self.next.val = data


class SingleLinkedList(object):
    """
    Single Linked List object
    Args:
        data(Node): Node
    Attributes:
        head(Node): single LinkedList head
    """

    def __init__(self, data):
        self.head = data

    def __repr__(self):
        """
        :return:
        """
        cur = self.head
        s = ''
        while cur:
            s += f'{cur.val}->'
            cur = cur.next
        return s

    def __len__(self):
        cur, cnt = self.head, 0
        while cur:
            cnt += 1
            cur = cur.next
        return cnt

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return
        cur = self.head
        while cur.next: cur = cur.next
        cur.next = Node(data)

    def insert_before_key(self, key, data):
        cur = self.head
        prev = Node(None)
        while cur:
            if cur.val == key:
                node = Node(data)
                node.next = cur
                prev.next = node
                break
            prev = cur
            cur = cur.next
        self.head = prev.next

    def insert_after_key(self, key, data):
        cur = self.head
        while cur:
            if cur.val == key:
                node = Node(data)
                node.next = cur.next
                cur.next = node
            cur = cur.next

    def delete(self, key):
        if not self.head: return
        dummy = cur = self.head
        prev = None
        while cur:
            if cur.val == key and prev:
                prev.next = cur.next
                self.head = dummy
                return
            elif cur.val == key:
                self.head = cur.next
                return
            prev = cur
            cur = cur.next

    def search(self, key):
        cur = self.head
        while cur and cur.val != key:
            cur = cur.next
        return cur or None

    def reverse(self):
        cur = self.head
        prev = None
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        self.head = prev

Peilonrayz · Accepted Answer · 2019-03-16 05:20:47Z

All of your methods on Node are useless. Just use Node.val and Node.next like you already are.
insert_after_key is likely to insert the data multiple times if there are multiple keys. Given how insert_before_key works differently you should test you code with unittests.
Your code fails silently. I don't recommend this.
You can remove the looping from all your functions if you add add a _iter function.
You can remove the need to loop to fine the key in most of your functions if you add a _find_key function, which returns the previous and next node.
I'd implement (5) using pairwise (itertools recipe) and use the _iter function.
You can simplify append if you use the tail itertools recipe.
You don't seem to have much code to handle empty lists.

import collections
import itertools


def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = itertools.tee(iterable)
    next(b, None)
    return zip(a, b)


def tail(n, iterable):
    "Return an iterator over the last n items"
    # tail(3, 'ABCDEFG') --> E F G
    return iter(collections.deque(iterable, maxlen=n))


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


class SingleLinkedList(object):
    def __init__(self, data):
        self.head = data

    def __repr__(self):
        return '->'.join(str(n) for n in self._iter())

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

    def _iter(self):
        node = self.head
        while node is not None:
            yield node
            node = node.next

    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return

        last, = tail(self._iter(), 1)
        last.next = Node(data)

    def _find_key(self, key):
        if self.head is None:
            raise IndexError('Key not found')
        if key == self.head.value:
            return None, self.head

        for prev, curr in pairwise(self._iter()):
            if curr.val == key:
                return prev, curr
        raise IndexError('Key not found')

    def insert_before_key(self, key, data):
        prev, curr = self._find_key(key)
        if prev is None:
            self.head = Node(data, self.head)
        else:
            prev.next = Node(data, curr)

    def insert_after_key(self, key, data):
        _, node = self._find_key(key)
        node.next = Node(data, node.next)

    def delete(self, key):
        prev, curr = _find_key(key)
        if prev is None:
            self.head = curr.next
        else:
            prev.next = curr.next

    def search(self, key):
        _, node = _find_key(key)
        return node

    def reverse(self):
        cur = self.head
        prev = None
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        self.head = prev

thank you.couple fo questions, why use if prev is None or if self.head is None but not if not prev or if not self.head? — A.Lee
– A.Lee, Commented Mar 16, 2019 at 7:01
how to make reverse function without self.head =prev on last line? — A.Lee
– A.Lee, Commented Mar 16, 2019 at 7:12
@A.Lee I use if x is None for when I want to test if x is None. And use if x for when I want to test if x is truthy. Whilst you get the same outcome here, they have different meanings. You'll have to figure that second comment out on your own. — Peilonrayz
– Peilonrayz ♦, Commented Mar 16, 2019 at 14:24

Stack Exchange Network

Implement LinkedList class in python

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Implement LinkedList class in python

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions