CODEWITHSUNDEEP
pythonlist
Qman485
Qman485

Reputation: 115

removing an element from a linked list in python

I was wondering if any of you could give me a walk through on how to remove an element from a linked list in python, I'm not asking for code but just kinda a pseudo algorithm in english. for example I have the linked list of 1 -> 2 -> 2 -> 3 -> 4 and I want to remove one of the 2's how would i do that? I thought of traversing through the linked list, checking to see if the data of one of the nodes is equal to the data of the node after it, if it is remove it. But I'm having trouble on the removing part. Thanks!

Upvotes: 2

Views: 6581

Answers (6)

user21782766
user21782766

Reputation: 1

If you need to remove an element from the linked list, using index, you may do this like that:

def remove(self, index):
    cur_node = self.head
    cur_index = 0

    if cur_node is None:
        if index == 0:
            self.head = cur_node.next
            self.length -= 1
            return

    while cur_node is not None:
        if cur_index == index:
            break
        prev = cur_node
        cur_node = cur_node.next
        cur_index += 1

    if cur_node == None:
        return

    prev.next = cur_node.next
    cur_node = None
    self.length -= 1

Upvotes: 0

dejanualex
dejanualex

Reputation: 4328

If you want to implement list-like container with fast appends and pops on either end I highly recommend deque module from containers library https://docs.python.org/2/library/collections.html

Upvotes: 0

venkat
venkat

Reputation: 161

You need to maintain two pointers

  1. One is to check whether the current node's data is same as the value to be deleted
  2. The other pointer is to keep the reference of the previous node to the current node. This is required because when you delete the current node, the current node's next one needs to be pointed to the current node's previous one.

Here is the code to do the same in python:

def remove(self, val):
    if self.head == val:
        self.head = self.head.next
        return

    tmp = self.head.next
    tmp_prev = self.head

    while tmp.next is not None:
        if tmp.data == val:
             tmp_prev.next = tmp.next
        tmp = tmp.next
        tmp_prev = tmp.next

    return

Upvotes: 1

Henry Zhu
Henry Zhu

Reputation: 2618

Instead of deleting the element, all you need to do is change the pointer. For example, you want the previous element of the node you want to delete to point to the element after the element you want to delete:

node is what you want to delete

node.parent.next = node.next

Upvotes: 1

Tales Pádua
Tales Pádua

Reputation: 1461

You can do something like:

if element.next.value == element.value: element.next = element.next.next

Just be carefull to free the memory if you are programing this in C/C++ or other language that does not have GC

Upvotes: 0

user1717828
user1717828

Reputation: 7225

You don't need to "delete" the node, just "skip" it. That is, change Node1's next member to the second Node2.

Edit your question if you would like specific code examples (which are the norm for this site).

Upvotes: 0

Related Questions