Removing a node from a linked list

I would like to create a delete_node function that deletes the node at the location in the list as a count from the first node. So far this is the code I have:

class node:
    def __init__(self):
        self.data = None # contains the data
        self.next = None # contains the reference to the next node

class linked_list:
    def __init__(self):
        self.cur_node = None

    def add_node(self, data):
        new_node = node() # create a new node
        new_node.data = data
        new_node.next = self.cur_node # link the new node to the 'previous' node.
        self.cur_node = new_node #  set the current node to the new one.

    def list_print(self):
        node = ll.cur_node
        while node:
            print node.data
            node = node.next
    def delete_node(开发者_开发百科self,location):
        node = ll.cur_node
        count = 0
        while count != location:
            node = node.next
            count+=1
        delete node


ll = linked_list()
ll.add_node(1)
ll.add_node(2)
ll.add_node(3)

ll.list_print()

You shouldn't literally delete a node in Python. If nothing points to the node (or more precisely in Python, nothing references it) it will be eventually destroyed by the virtual machine anyway.

If n is a node and it has a .next field, then:

n.next = n.next.next 

Effectively discards n.next, making the .next field of n point to n.next.next instead. If n is the node before the one you want to delete, this amounts to deleting it in Python.

[P.S. the last paragraph may be a bit confusing until you sketch it on paper - it should then become very clear]

Here's one way to do it.

def delete_node(self,location):
    if location == 0:
        try:
            self.cur_node = cur_node.next
        except AttributeError:
            # The list is only one element long
            self.cur_node = None
        finally:
            return 

    node = self.cur_node        
    try:
        for _ in xrange(location):
            node = node.next
    except AttributeError:
        # the list isn't long enough
        raise ValueError("List does not have index {0}".format(location))

    try:
        node.next = node.next.next # Taken from Eli Bendersky's answer.
    except AttributeError:
        # The desired node is the last one.
        node.next = None

The reason that you don't really use del (and this tripped me up here until I came back and looked at it again) is that all it does is delete that particular reference that it's called on. It doesn't delete the object. In CPython, an object is deleted as soon as there are no more references to it. What happens here that when

del node

runs, there are (at least) two references to the node: the one named node that we are deleting and the next attribute of the previous node. Because the previous node is still referencing it, the actual object is not deleted and no change occurs to the list at all.

# Creating a class node where the value and pointer is stored
# initialize the id and name parameter so it can be passed as Node(id, name)
class Node:
    def __init__(self, id, name):
        # modify this class to take both id and name
        self.id = id
        self.name = name
        self.next = None


# Create a class linkedlist to store the value in a node
class LinkedList:

    # Constructor function for the linkedlist class
    def __init__(self):
        self.first = None

    # This function inserts the value passed by the user into parameters id and name
    # id and name is then send to Node(id, name) to store the values in node called new_node
    def insertStudent(self, id, name):
        # modify this function to insert both id and names as in Q1
        new_node = Node(id, name)
        new_node.next = self.first
        self.first = new_node

    # We will call this function to remove the first data in the node
    def removeFirst(self):
        if self.first is not None:
            self.first = self.first.next

    # This function prints the length of the linked list
    def length(self):
        current = self.first
        count = 0
        while current is not None:
            count += 1
            current = current.next
        return count

    # This function prints the data in the list
    def printStudents(self):
        # modify this function to print the names only as in Q2.
        current = self.first
        while current is not None:
            print(current.id, current.name)
            current = current.next

    # This function lets us to update the values and store in the linked list
    def update(self, id):
        current = self.first
        while current is not None:
            if (current.id == id):
                current.id = current.id.next
            # print(current.value)
            current = current.next

    # This function lets us search for a data and flag true is it exists
    def searchStudent(self, x, y):
        current = self.first
        while current is not None:
            if (current.id == x and current.name == y):
                return True
            current = current.next

    # This function lets us delete a data from the node
    def delStudent(self,key):
         cur = self.node

        #iterate through the linkedlist
        while cur is not None: 

        #if the data is in first node, delete it
            if (cur.data == key):
                self.node = cur.next
                return

        #if the data is in other nodes delete it
            prev = cur
            cur = cur.next
            if (cur.data == key):
                prev.next = cur.next
                return

            # Initializing the constructor to linked list class

my_list = LinkedList()

# Adding the ID and Student name to the linked list
my_list.insertStudent(101, "David")
my_list.insertStudent(999, "Rosa")
my_list.insertStudent(321, "Max")
my_list.insertStudent(555, "Jenny")
my_list.insertStudent(369, "Jack")

# Print the list of students
my_list.printStudents()

# Print the length of the linked list
print(my_list.length(), " is the size of linked list ")

# Search for a data in linked list
if my_list.searchStudent(369, "Jack"):
    print("True")
else:
    print("False")

# Delete a value in the linked list
my_list.delStudent(101)

# Print the linked list after the value is deleted in the linked list
my_list.printStudents() 

I did the pop() function using a recursive function because the iterative way with references it's not so good. So the code is below. I hope this help you! ;)

class Node:

  def __init__(self, data=0, next=None):
    self.data = data
    self.next = next

  def __str__(self):
    return str(self.data)


class LinkedList:

    def __init__(self):
        self.__head = None
        self.__tail = None
        self.__size = 0

    def addFront(self, data):
        newNode = Node(data, self.__head)
        if (self.empty()):
            self.__tail = newNode  
        self.__head = newNode
        self.__size += 1

    def __str__(self):
        # retorno deve ser uma string:
        s = "["
        node = self.__head
        while node:
            s += str(node.data) + ' ' if node.next != None else str(node.data)
            node = node.next
        return s + "]"



    def __recPop(self, no, i, index):
        if (i == index-1):

            if (index == self.size() - 1):
                self.__tail = no
            try:
                no.next = no.next.next; 
            except AttributeError:
                no.next  = None
            
        else: 
            self.__recPop(no.next, i+1, index)

        
    def pop(self, index=0):

        if (index < 0 or index >= self.__size or self.__size == 0):
            return

        if (index == 0):
            try:
                self.__head = self.__head.next
            except AttributeError:
                self.__head  = None
                self.__tail  = None
            
        else:
            self.__recPop(self.__head, 0, index)
        
        self.__size -= 1
                
    def front(self):
        return self.__head.data

    def back(self):
        return self.__tail.data

    def addBack(self, data):
        newNode = Node(data)
        if (not self.empty()):
            self.__tail.next = newNode
        else:
            self.__head = newNode

        self.__tail = newNode
        self.__size += 1

    def empty(self):
        return self.__size == 0

    def size(self):
        return self.__size

    

    def __recursiveReverse(self, No):
        if No == None : return
        self.__recursiveReverse(No.next)
        print(No, end=' ') if self.__head != No else print(No, end='')

    def reverse(self):
        print('[', end='')
        self.__recursiveReverse(self.__head)
        print(']')

def remove(self,data):
 current = self.head;
 previous = None;
 while current is not None:
  if current.data == data:
    # if this is the first node (head)
    if previous is not None:
      previous.nextNode = current.nextNode
    else:
      self.head = current.nextNode
  previous = current
  current = current.nextNode;

Python lists are linked lists.

thelist = [1, 2, 3]
# delete the second
del thelist[2]

Assume Linked List has more than 1 nodes. such as n1->n2->n3, and you want to del n2.

n1.next = n1.next.next
n2.next = None

If you want to del n1, which is the head.

head = n1.next
n1.next = None

This is how I did it.

def delete_at_index(self, index):
    length = self.get_length()
    # Perform deletion only if the index to delete is within or equal to the length of the list.
    if index<=length:
        itr = self.head
        count = 0

        # If the index to delete is zeroth.
        if count==index:
            self.head = itr.next
            return
        
        while itr.next:
            if count==index-1:
                try:
                    # If the index to delete is any index other than the first and last.
                    itr.next = itr.next.next
                except:
                    # If the index to delete is the last index.
                    itr.next = None
                return
            count+=1
            itr = itr.next

def get_length(self):
    itr = self.head
    count = 0
    while itr:
        count += 1
        itr = itr.next
    return count