Delete smaller nodes in linked list in Python

Given a singly linked list and a position, delete a linked list node at the given position.

Nội dung chính Show

Video liên quan

Example:

Input: position = 1, Linked List = 8->2->3->1->7 Output: Linked List = 8->3->1->7 Input: position = 0, Linked List = 8->2->3->1->7 Output: Linked List = 2->3->1->7

If node to be deleted is root, simply delete it. To delete a middle node, we must have pointer to the node previous to the node to be deleted. So if positions is not zero, we run a loop position-1 times and get pointer to the previous node.

Below is the implementation of above idea.

C/C++

// A complete working C program to delete a node in a linked list

// at a given position

#include

// A linked list node

struct Node

{

int data;

struct Node *next;

};

/* Given a reference (pointer to pointer) to the head of a list

and an int, inserts a new node on the front of the list. */

void push(struct Node** head_ref,int new_data)

{

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

new_node->data = new_data;

new_node->next = (*head_ref);

(*head_ref) = new_node;

}

/* Given a reference (pointer to pointer) to the head of a list

and a position, deletes the node at the given position */

void deleteNode(struct Node **head_ref,int position)

{

// If linked list is empty

if (*head_ref == NULL)

return;

// Store head node

struct Node* temp = *head_ref;

// If head needs to be removed

if (position == 0)

{

*head_ref = temp->next;// Change head

free(temp);// free old head

return;

}

// Find previous node of the node to be deleted

for (int i=0; temp!=NULL && i

temp = temp->next;

// If position is more than number of ndoes

if (temp == NULL || temp->next == NULL)

return;

// Node temp->next is the node to be deleted

// Store pointer to the next of node to be deleted

struct Node *next = temp->next->next;

// Unlink the node from linked list

free(temp->next);// Free memory

temp->next = next;// Unlink the deleted node from list

}

// This function prints contents of linked list starting from

// the given node

void printList(struct Node *node)

{

while (node != NULL)

{

printf(" %d ", node->data);

node = node->next;

}

/* Drier program to test above functions*/

int main()

{

/* Start with the empty list */

struct Node* head = NULL;

push(&head, 7);

push(&head, 1);

push(&head, 3);

push(&head, 2);

push(&head, 8);

puts("Created Linked List: ");

printList(head);

deleteNode(&head, 4);

puts(" Linked List after Deletion at position 4: ");

printList(head);

return 0;

}

Java

// A complete working Java program to delete a node in a linked list

// at a given position

class LinkedList

{

Node head;// head of list

/* Linked list Node*/

class Node

{

int data;

Node next;

Node(int d)

{

data = d;

next =null;

}

/* Inserts a new Node at front of the list. */

public void push(int new_data)

{

/* 1 & 2: Allocate the Node &

Put in the data*/

Node new_node =new Node(new_data);

/* 3. Make next of new Node as head */

new_node.next = head;

/* 4. Move the head to point to new Node */

head = new_node;

}

/* Given a reference (pointer to pointer) to the head of a list

and a position, deletes the node at the given position */

void deleteNode(int position)

{

// If linked list is empty

if (head ==null)

return;

// Store head node

Node temp = head;

// If head needs to be removed

if (position ==0)

{

head = temp.next;// Change head

return;

}

// Find previous node of the node to be deleted

for (int i=0; temp!=null && i

temp = temp.next;

// If position is more than number of ndoes

if (temp ==null || temp.next ==null)

return;

// Node temp->next is the node to be deleted

// Store pointer to the next of node to be deleted

Node next = temp.next.next;

temp.next = next;// Unlink the deleted node from list

}

/* This function prints contents of linked list starting from

the given node */

public void printList()

{

Node tnode = head;

while (tnode !=null)

{

System.out.print(tnode.data+" ");

tnode = tnode.next;

}

/* Drier program to test above functions. Ideally this function

should be in a separate user class. It is kept here to keep

code compact */

public static void main(String[] args)

{

/* Start with the empty list */

LinkedList llist =new LinkedList();

llist.push(7);

llist.push(1);

llist.push(3);

llist.push(2);

llist.push(8);

System.out.println(" Created Linked list is: ");

llist.printList();

llist.deleteNode(4);// Delete node at position 4

System.out.println(" Linked List after Deletion at position 4: ");

llist.printList();

}

Python

# Python program to delete a node in a linked list

# at a given position

# Node class

class Node:

# Constructor to initialize the node object

def __init__(self, data):

self.data= data

self.next = None

class LinkedList:

# Constructor to initialize head

def __init__(self):

self.head= None

# Function to insert a new node at the beginning

def push(self, new_data):

new_node= Node(new_data)

new_node.next = self.head

self.head= new_node

# Given a reference to the head of a list

# and a position, delete the node at a given position

def deleteNode(self, position):

# If linked list is empty

if self.head== None:

return

# Store head node

temp= self.head

# If head needs to be removed

if position== 0:

self.head= temp.next

temp= None

return

# Find previous node of the node to be deleted

for iin range(position-1 ):

temp= temp.next

if tempis None:

break

# If position is more than number of nodes

if tempis None:

return

if temp.next is None:

return

# Node temp.next is the node to be deleted

# store pointer to the next of node to be deleted

next = temp.next.next

# Unlink the node from linked list

temp.next = None

temp.next = next

# Utility function to print the linked LinkedList

def printList(self):

temp= self.head

while(temp):

print " %d " %(temp.data),

temp= temp.next

# Driver program to test above function

llist= LinkedList()

llist.push(7)

llist.push(1)

llist.push(3)

llist.push(2)

llist.push(8)

print "Created Linked List: "

llist.printList()

llist.deleteNode(4)

print " Linked List after Deletion at position 4: "

llist.printList()

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

/div>

Output:Created Linked List: 8 2 3 1 7 Linked List after Deletion at position 4: 8 2 3 1

Thanks to Hemanth Kumar for suggesting initial solution. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Top List List

Delete smaller nodes in linked list in Python

C/C++

Java

Python

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội