Singly linked list operations in C/C++ using ChatGPT
Last time, a singly linked list node and create a list without defining operations such as add behind, add in front, delete and search. This article shows how to implement singly linked list operations in C/C++ using ChatGPT. I search “singly linked list operations in C”. It writes header file to provide all function prototypes.
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
};
// Function prototypes
void insertAtBeginning(struct Node** head, int data);
void insertAtEnd(struct Node** head, int data);
void insertAtPosition(struct Node** head, int data, int position);
void deleteNode(struct Node** head, int key);
void displayList(struct Node* head);
First question would be why we need to use a double pointer? Double pointers in linked lists are primarily used to modify the head pointer of the list directly within a function. insertAtBeginning, insertAtEnd, insertAtPosition, deleteNode are using a double pointer. However, a double pointer is C language specific thing and conceptually this can be written without using a double pointer.
Let’s search “singly linked list operation without double pointer in C”. Main difference is each function’s return type. With a double pointer, return type is the void. Without a double pointer, return type is Node pointer. First, insertAtBeginning function comparison below:
//With double pointer
void insertAtBeginning(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = *head;
*head = newNode; //C language expert will catch this line without a mistake!
}
//Without double pointer
struct Node* insertAtBeginning(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = head;
return newNode; // New head
} //This code seems more straightforward
Second, insertAtEnd function comparison below:
//With double pointer
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
struct Node* temp = *head;
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) { // If the list is empty
*head = newNode; //C language expert will catch this line without a mistake!
return;
}
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
//Without double pointer
struct Node* insertAtEnd(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL) {
return newNode; // If list was empty, new node is now the head
}
struct Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
return head; // Return unchanged head
}
Third, insertAtPosition function comparison below and found interesting difference here is “with double pointer” version does not free the dynamically allocated memory when position is out of bounds. This is obviously causing the memory leak with repetition. This is reason why recently white house discourage to develop software with C/C++ because of no garbage collection. Even AI made a mistake to not free the memory when that is no where to use.
//With double pointer
void insertAtPosition(struct Node** head, int data, int position) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (position == 1) { // Insert at beginning
newNode->next = *head;
*head = newNode;
return;
}
struct Node* temp = *head;
for (int i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf("Position out of bounds\n");
//?????????????????????????????????Memory leak??????????????????????????????
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
//Without double pointer
struct Node* insertAtPosition(struct Node* head, int data, int position) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (position == 1) { // Insert at beginning
newNode->next = head;
return newNode;
}
struct Node* temp = head;
for (int i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) {
printf("Position out of bounds\n");
free(newNode);
return head;
}
newNode->next = temp->next;
temp->next = newNode;
return head;
}
Fourth, deleteNode comparison below and does not found anything interesting. Looks all good:
//With double pointer
void deleteNode(struct Node** head, int key) {
struct Node* temp = *head, *prev = NULL;
if (temp != NULL && temp->data == key) { // If head node contains the key
*head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) { // Search for the key
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
printf("Key not found\n");
return;
}
prev->next = temp->next; // Unlink the node
free(temp);
}
//Without double pointer
struct Node* deleteNode(struct Node* head, int key) {
struct Node* temp = head, *prev = NULL;
if (temp != NULL && temp->data == key) { // If head node contains the key
head = temp->next;
free(temp);
return head;
}
while (temp != NULL && temp->data != key) { // Search for the key
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
printf("Key not found\n");
return head;
}
prev->next = temp->next; // Unlink the node
free(temp);
return head;
}
displayList does not use a double pointer and there is no difference between two versions!
void displayList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
//With double pointer
int main() {
struct Node* head = NULL;
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
insertAtEnd(&head, 30);
insertAtPosition(&head, 25, 2);
printf("Linked List: ");
displayList(head);
deleteNode(&head, 20);
printf("After Deletion: ");
displayList(head);
return 0;
}
//Without double pointer
int main() {
struct Node* head = NULL;
head = insertAtBeginning(head, 10);
head = insertAtBeginning(head, 20);
head = insertAtEnd(head, 30);
head = insertAtPosition(head, 25, 2);
printf("Linked List: ");
displayList(head);
head = deleteNode(head, 20);
printf("After Deletion: ");
displayList(head);
return 0;
}
If anybody realizes no C++ code in this article? Without double pointer version, it is easy to transform in C++ code after defining Node as a class.
#include <iostream>
using namespace std;
// Node class
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = nullptr;
}
};
Every return type can be replaced with Node*. Instead of using “malloc”, C++ would use “new” keyword. Also, instead of using “free”, C++ would use “delete” keyword. Here is an example:
Node* insertAtBeginning(Node* head, int data) {
Node* newNode = new Node(data);
newNode->next = head;
return newNode; // New head
}
Node* insertAtPosition(Node* head, int data, int position) {
Node* newNode = new Node(data);
if (position == 1) { // Insert at beginning
newNode->next = head;
return newNode;
}
Node* temp = head;
for (int i = 1; i < position - 1 && temp != nullptr; i++) {
temp = temp->next;
}
if (temp == nullptr) {
cout << "Position out of bounds\n";
delete newNode;
return head;
}
newNode->next = temp->next;
temp->next = newNode;
return head;
}
These days, many developers require to use multiple programming language to their job done. Language specific syntax or concept is not universal and I personally want to avoid those situations. Using ChatGPT to write two different version, even though C and C++ are similar each other, there are language specific keywords to be distinguished but logic. In C++, it does not recommend to use pointer even though it is acceptable in syntax by inheritance from C. To show where to misuse pointers, I started to compare with double pointer and single pointer version because there is less chance to misuse single pointer than double pointer. Also, it is interesting that ChatGPT forgot to free the unused dynamically allocated memory. To avoid this situation, the developer can save time to write code with AI but still needs to pay attention to test enough to confirm all functionalities as well as complying memory safe.