5
\$\begingroup\$

I know this implementation is very bare-bones, but are there any improvements I can make to it? (E.g. more pythonic, style, speed, comments).

I was considering using @property decorators a bit more, but I thought that was overkill for this example.

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

    def __str__(self):
        return "Node Object : val {}".format(self.value)

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

    @property
    def length(self):
        if self.head is None:
            return 0
        length = 1
        current = self.head
        while current.next is not None:
            current = current.next
            length += 1
        return length

    def append(self, node):
        if self.head is None:
            self.head = node
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = node

    def prepend(self, node):
        if self.head is None:
            self.head = node
            return
        node.next = self.head
        self.head = node

    def get(self, index):
        current = self.head
        for i in range(0, index):
            if current.next is not None:
                current = current.next
            else:
                return None
        return current

    def delete(self, val):
        if self.head.value is val:
            self.head = None
            return
        current = self.head
        while current.next is not None:
            if current.next.value is val:
                current.next = current.next.next
                return
            current = current.next
\$\endgroup\$
4
\$\begingroup\$

There are a couple of things to consider.

Pythonic Attributes

Using built-in functions

You have defined your own version of list.length, but Python provides a built-in function __len__(). So you could change:

@property
def length(self):
    # some code

to:

def __len__(self):
    # some code

Also, you could override the built-in __str__() function to visualize your list:

def __str__(self):
     nodes = []
     temp = self.head
     for i in range(self.length):
         nodes.append(str(temp.value))
         temp = temp.next
     return ' --> '.join(nodes) 

Also, you can implement an iterator:

def __init__(self):
    self.head = None
    self.iter_ref = self.head 
    self.itered = False

def __iter__(self):
    return self

def __next__(self):
    if self.iter_ref is None and self.itered:
        self.itered = False
        raise StopIteration
    else:
        if self.iter_ref is None and not self.itered:
            self.iter_ref = self.head
            self.itered = True
        ret_val = self.iter_ref.value
        self.iter_ref = self.iter_ref.next
        return ret_val

Also, there is a built-in function for get() called __getitem()__. It takes, the same parameters as your function.

Convenience

One more thing, instead of taking in a Node as a parameter for your LinkedList functions, consider just taking in the raw data type. That means you just need to change the first two lines of the prepend() and append() to look like (for example):

def append(self, data):
    node = Node(data)
    # rest of the implementation

So now, to use your code, you can do the following:

ll = LinkedList()
ll.append(1)
ll.prepend(3)
print(len(ll))  # prints "2"
print(str(ll))  # prints "3 --> 1"
print(ll[0])    # prints "3"
print(list(ll)) # prints "[3, 1]"

Optimizations

If you decided to take in raw data types as mentioned above, you can now perform these optimizations:

Computation of Length

Rather than iterate through the entire list every time you need the length, just keep the length as a member variable and increment/decrement it accordingly. Make sure to initialize self.length = 0 in your constructor, then in your append() and prepend() methods, make sure to increment the length, and in your delete() method, make sure to decrement the length when you actually delete a Node. Then, your __len__() method can just look like:

def __len__(self):
    return self.length

Append

Also, your append() function could be optimized by keeping a pointer to the tail rather than iterating to the tail each time:

def append(self, data):
    node = Node(data)
    if self.head is None:
        self.head = self.tail = node
    else:
        self.tail.next = node
        self.tail = node
    self.length += 1

def prepend(self, data):
    node = Node(data)
    if self.head is None:
        self.head = self.tail = node
    else:
        node.next = self.head
        self.head = node
    self.length += 1

Make sure to add self.tail = None in your constructor as well.

Here is the code that I suggested:

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

    def __str__(self):
        return "Node Object : val {}".format(self.value)

class LinkedList:
    def __init__(self):
        self.head = self.tail = None
        self.length = 0
        self.iter_ref = self.head
        self.itered = False


    def __len__(self):
        return self.length

    def __str__(self):
        nodes = []
        temp = self.head
        for i in range(self.length):
            nodes.append(str(temp.value))
            temp = temp.next
        return ' --> '.join(nodes)

    def __iter__(self):
        return self

    def __next__(self):
        if self.iter_ref is None and self.itered:
            self.itered = False
            raise StopIteration
        else:
            if self.iter_ref is None and not self.itered:
                self.iter_ref = self.head
                self.itered = True
            ret_val = self.iter_ref.value
            self.iter_ref = self.iter_ref.next
            return ret_val

    def append(self, data):
        node = Node(data)
        if self.head is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.length += 1

    def prepend(self, data):
        node = Node(data)
        if self.head is None:
            self.head = self.tail = node
        else:
            node.next = self.head
            self.head = node
        self.length += 1

    def __getitem__(self, index):
        current = self.head
        for i in range(index):
            if current.next is not None:
                current = current.next
            else:
                return None
        return current.value

    def delete(self, val):
        if self.head.value is val:
            self.head = None
            self.length -= 1
            return
        current = self.head
        while current.next is not None:
            if current.next.value is val:
                current.next = current.next.next
                self.length -= 1
                return
            current = current.next
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.