#linked list

[hauxicrook]

Just finished a code of 200 lines and now i have to write it in LAB FILE!!!

BC! ye kya baat hui bhai !!! CLG should understand this T-T

[wobinbug]

I decided to sit my ass down and learn what a linked list is finally 🫣

It was shockingly uncomplicated 💀

I ended up implementing my own doubly linked list for integers in C and it was super helpful for understanding the data structure as well as a nice reminder about using pointers and manual memory allocation.

Of course, I wrote a few functions to do the following:

- Add to start of list

- Add to end of list

- Remove from start of list

- Remove from end of list

- Delete specific value

Of course, there's much more I can do, but I'm happy with where I'm at so far. Definitely a good exercise to get back into things before uni starts properly 😁

[webthreecorp]

Mastering Linked Lists: Beginner's Guide

Hey Tumblr friends 👋

After learning about Arrays, it's time to level up! Today we’re diving into Linked Lists — another fundamental building block of coding! 🧱✨

So... What is a Linked List? 🤔

Imagine a treasure hunt 🗺️:

You find a clue ➡️ it points you to the next clue ➡️ and so on.

That's how a Linked List works!

🔗 Each element (Node) holds data and a pointer to the next Node.

It looks something like this: [data | next] -> [data | next] -> [data | next] -> NULL

Why Use a Linked List? 🌈

✅ Dynamic size (no need to pre-define size like arrays!) ✅ Easy insertions and deletions ✨ ✅ Great for building stacks, queues, and graphs later!

❌ Slower to access elements (you can't jump straight to an item like arrays).

Basic Structure of a Linked List Node 🛠️

data -> stores the actual value

next -> points to the next node

📚 CRUD Operations on Linked Lists

Let’s build simple CRUD functions for a singly linked list in C++! (🚀 CRUD = Create, Read, Update, Delete)

Create (Insert Nodes)

Read (Display the list)

Update (Change a Node’s Value)

Delete (Remove a Node)

🌟 Final Thoughts

🔗 Linked Lists may look tricky at first, but once you master them, you’ll be ready to understand more powerful structures like Stacks, Queues, and even Graphs! 🚀

🌱 Mini Challenge:

Build your own linked list of your favorite songs 🎶

Practice inserting, updating, and deleting songs!

If you loved this explainer, give a follow and let's keep leveling up together! 💬✨ Happy coding, coder fam! 💻🌈 For more resources and help join our discord server

Here, we grow together — whether you are just starting out or leveling up your skills.🚀 What You Can Learn Here:💻 Web Development (Frontend

[hedome]

Etymology, English, List

Etymology Noun. From Middle English lī̆st, lī̆ste (“band, stripe; hem, selvage; border, edge, rim; list, specification; barriers enclosing area for jousting, etc.”), from Old English līste (“hem, edge, strip”), or Old French liste, listre (“border; band; strip of paper; list”), or Medieval Latin lista, all from Proto-Germanic *līstǭ (“band, strip; hem, selvage; border, edge”), possibly…

View On WordPress

[educationforallblog-blog]

Data Structure and Algorithm Complete Tutorial Made Easy by Computer Education For All 

[lab-01]

Length of a Circular Linked List

length (p){ c=0; if (p) { t = p;

do{ c++; t = t -> next; } while(t != p); } return c; }

[lab-01]

Linked List

why is linked list called dynamic?

Linked lists are referred to as "dynamic" data structures primarily because of their flexibility in memory allocation and their ability to grow or shrink in size during runtime without needing a pre-defined capacity.

Here's why they are considered dynamic:

• No Pre-defined Size Required: Unlike arrays, where the number of elements must be known beforehand to allocate a contiguous block of memory, linked lists do not require the number of elements to be specified at the outset. This means you don't need to estimate or pre-allocate a fixed amount of memory that might be too much or too little.

• Flexible Insertion and Deletion: Linked lists excel in insertion and deletion operations because they do not require physical memory shifts or reallocations. When you add a new node, memory is dynamically allocated for that single node, and then pointers are simply updated to link it into the list. Similarly, when deleting a node, you just update pointers to bypass the node and then free its memory. This contrasts with arrays, where inserting or deleting an element might necessitate shifting many subsequent elements to maintain contiguity, which can be inefficient for large datasets.

• Non-contiguous Memory Allocation: Elements (nodes) in a linked list are not necessarily stored in contiguous memory locations. Instead, each node contains a pointer to the memory address of the next node. This allows linked list nodes to be scattered throughout memory, making efficient use of available memory blocks as needed, rather than requiring one large, continuous block.

In essence, the "dynamic" nature of linked lists stems from their design, which allows for efficient memory management and flexible size adjustments as data is added or removed, without the rigid constraints of fixed-size arrays.

Print List (O(n)) Operation

• Functionality and Mechanism: The print-list function is designed to print the data of the linked list starting from its head. It uses a pointer, typically named p, which is initialized to point to the head of the list. The function then enters a loop that continues as long as p is not NULL (which signifies the end of the list). Inside the loop, it accesses and prints the data component of the current node (p -> data), and then moves p to the next node (p = p -> next). This process ensures that every node in the list is visited and its data is displayed exactly once.

• Time Complexity (O(n)): The operation's time complexity is O(n) because it must traverse every node in the list to print all its contents. If the list has 'n' elements, the loop will iterate 'n' times, making the time taken directly proportional to 'n'.

The print-list function demonstrates the most basic form of sequential traversal: • Initialization: A pointer p is initialized to the head of the list. • Loop Condition: The loop continues as long as p is not NULL. NULL signifies the end of the list. • Data Access and Advancement: Inside the loop, the data component of the current node (p -> data) is accessed and printed. Then, p is moved to the next node by assigning p = p -> next. This process ensures every node is visited.

Print in reverse vs actually Reverse list - (O(n)) Operation

• Base Case: If p is NULL (i.e., !p), the function simply returns, stopping further recursion. • Recursive Step: It first calls itself with f(p -> next), effectively traversing to the end of the list through recursive calls. • Printing: After the recursive call returns (meaning it has reached the end or a later node), it then prints p -> data. This unwinding of the call stack causes the data to be printed in reverse order.

• Time Complexity: This recursive function also has a time complexity of O(n), as it still processes each node.

Code snippet 1: Reverse singly linked list recursively

c

struct Node { int data; struct Node* next; }; struct Node* reverseList(struct Node* head) { if (head == NULL | | head->next == NULL) return head; struct Node* revHead = reverseList(head->next); head->next->next = head; head->next = NULL; return revHead; }

What it does: This function recursively reverses a singly linked list and returns the new head of the reversed list.

How it works:

Base case: if head is NULL or only one node, return it.

Recursively reverse the rest of the list.

Adjust pointers to make the head->next node point back to head, then set head->next to NULL to cut the original link.

Return the reversed list's head.

Code snippet 2: Print linked list in reverse order recursively

c

struct Node { int data; struct Node* next; }; void printReverse(struct Node* p) { if (p == NULL) return; printReverse(p->next); printf("%d ", p->data); }

What it does: This function prints the linked list elements in reverse order, but does not modify the list.

How it works:

Base case: if the pointer is NULL, return.

Recursively call itself on the next node (to get to the end first).

When recursion unwinds, print the current node's data, so it prints in reverse order.

How are they similar?

Both use recursion to process the list.

Both reach the end of the list first (recursive calls go towards the tail).

Both rely on the natural call stack to handle elements in reverse order.

Both have a base case when the pointer is NULL.

How are they different?

Aspect: Purpose

reverseList: Reverse the linked list by modifying links

printReverse: Print data in reverse without modifying the list

Aspect: Return value

reverseList: Returns the new head of the reversed list

printReverse: Returns void (no changes made to list)

Aspect: Side effects

reverseList: Changes the next pointers in the list (mutates list structure)

printReverse: No mutation; only prints data

Aspect: Output

reverseList: Returns a pointer to the reversed list head

printReverse: Prints elements to stdout

Aspect: Complexity

Both have time complexity O(n) and require O(n) stack space due to recursion

Summary

Both are recursive functions operating on a singly linked list. The main difference is:

The first one actually reverses the list by changing pointers.

The second one just prints the list in reverse order by visiting nodes recursively without altering the list.

see also!

another code for actually reversing the list; this time without using recursion:

Reversing a Singly Linked List (O(n))

The core idea behind reversing a singly linked list, as described in the sources, is to change the next pointer of each node to point to its previous node. This process is achieved by systematically updating pointers as the list is traversed.

• Pointers Used: The reverse function utilizes three essential pointers: p, q, and t.

    ◦ q typically points to the current node being processed.

    ◦ p points to the previous node (the one that q's next pointer should point to after reversal).

    ◦ t points to the next node in the original sequence (used to advance q after its next pointer has been changed).

• Initialization: Initially, p is null (as there's no node before the first node), q points to the head of the list, and t points to q's next node.

• Reversal Loop: The process occurs within a while loop that continues as long as t is not null. Inside the loop, the following steps happen in each iteration:

    1. The next component of the current node q is changed to point to p (q -> next = p;). This is the crucial step that reverses the link.

    2. p is advanced to q (p = q;). The current node q will become the "previous" node for the next iteration.

    3. q is advanced to t (q = t;). q moves to the next node in the original sequence.

    4. t is advanced to t -> next (t = t -> next;). t keeps track of the node after the new q for the next iteration.

• After the Loop: Once t becomes null, it signifies that all nodes except the last one (which is now pointed to by q) have had their next pointers reversed. The next pointer of the final node (which q points to) is then set to p (q -> next = p;).

• Return Value: The function then returns q, which now points to the new head of the reversed list (the original tail).

• Time Complexity: This operation is performed in linear time, O(n), where 'n' is the number of elements in the list. This is because each node in the list is visited and processed exactly once.

Reversal in the Context of Linked List Operations

Reversing a list is a transformative operation that fundamentally alters the structure of the linked list by redirecting all its pointers.

Let's walk through this function step by step with a simple example.

Suppose you have a linked list like this: 1 -> 2 -> 3 -> NULL

Initial State:

head points to the first node (value 1)

p = NULL

q = head (1)

t = q->next (2)

First iteration of while loop:

q = 1, t = 2

q->next = p sets 1's next to NULL (breaking the link with 2)

p = 1

q = t (2)

t = t->next (3)

Now you have:

1 -> NULL (in my head it's NULL <- 1)

2 -> 3 -> NULL

Second iteration:

q = 2, t = 3

q->next = p sets 2's next to 1 (reverse the link)

p = 2

q = t (3)

t = t->next (NULL)

Now you have:

2 -> 1 -> NULL

3 -> NULL

Loop ends (t == NULL), but q is still at 3:

q = 3

q->next = p sets 3's next to 2 (reverse the link)

Done! q is now the head of the reversed list

Final list: 3 -> 2 -> 1 -> NULL

return q; returns the new head (3).

Node Insertion

insert node n after node p

• A new node, n, is dynamically allocated in memory using malloc(sizeof(node)).

• The data field of this new node n is set to the item value.

• The next pointer of the new node n is made to point to the same node that p's next pointer was previously pointing to (i.e., n -> next = p -> next;). This ensures the new node is correctly linked into the existing sequence.

• Finally, the next pointer of the node p is updated to point to the newly inserted node n (i.e., p -> next = n;).

Node Insertion in Doubly Linked Lists

(not using the original p - > next. I mean we know it only as p - > next)

A doubly linked list enhances the node structure by adding a prev pointer in addition to the data and next pointers. This prev pointer points to the preceding node in the sequence, enabling traversal in both forward and backward directions.

When inserting a new node x to the right of a specified node p in a doubly linked list, four pointer changes are typically required to maintain the integrity of both forward and backward links:

• The prev pointer of the new node x is set to point to p (x -> prev = p;).

• The next pointer of the new node x is set to point to the node that p's next pointer was previously pointing to (x -> next = p -> next;).

• The prev pointer of the node that was originally after p (i.e., p -> next) is updated to point to the new node x (p -> next -> prev = x;).

• Finally, the next pointer of node p is updated to point to the new node x (p -> next = x;).

Deletion in Singly Linked Lists

• The delete function takes first (the head of the list), p (the node before the node to be deleted), and d (the node to be deleted, referred to by its address node * d) as arguments.

• The logic depends on whether p is NULL (meaning d is the first node) or not.

    ◦ If p is NULL (i.e., d is the head of the list), the first pointer of the list is updated to point to the node after d (i.e., *first = (*first) -> next;).

    ◦ If p is not NULL (i.e., d is not the head), the next pointer of node p is made to point to the node that d was pointing to (i.e., p -> next = d -> next;). This effectively bypasses d, removing it from the list's sequence.

• After adjusting the pointers, the memory occupied by node d is freed using free(d).

Deletion in Doubly Linked Lists

When deleting a node p from a doubly linked list, two pointer changes are required to maintain the integrity of the list:

• The next pointer of the node before p (p -> prev) is updated to point to the node after p (p -> next).

• The prev pointer of the node after p (p -> next) is updated to point to the node before p (p -> prev).

• Finally, the memory allocated for node p is freed using free(p).

Question:

Given a singly linked list and a node pointer d, write code to find the node x such that x->next == d, i.e., the node immediately before d.

Answer (C++ Code):

node* x = head; while (x != nullptr && x->next != nullptr) { if (x->next == d) { // Found the node before d break; } x = x->next; }

This code starts at the head of the list and iterates forward.

When it finds a node whose next points to d, it stops — x is now the node right before d.

The x != nullptr && x->next != nullptr condition ensures safe traversal.

Concatenation

node* concat ( node* head1, node* head2) { if (head1==NULL) return head2; else { if (head2!= NULL){ for (p = head1; p -> next != NULL ; p = p -> next ) ; p -> next = head2; } return head1; }

}

[sentientcanvas]

They just release a new data structure called kinked list