Learn DSA - Linked List

A singly linked list is a dynamically distributed collection of Nodes, arranged in such a way that each Node contains a value (Data) and a pointer (Next). The pointer will point to the next element of that linked list. If the pointer points to NULL, it is the last element of the linked list.

Content	Array	Linked List
Size	- Fixed size - Need to specify size during declaration	- Size changes during element addition/removal. - Maximum size depends on memory
Memory Allocation	Static: Memory allocated during compilation.	Dynamic: Memory allocated during run time.
Ordering and sorting	Stored in a contiguous array of memory cells.	Stored in random memory cells.
Accessing	Accessing random element directly using array index: O(1).	Accessing a random element requires traversing from the beginning/end to the element: O(n).
Searching	Linear search or binary search.	Only linear search is possible.

Type of linked list:

• Linked List.
• Doubly Linked List.
• Circular Linked List.

With other languages such as Java, C#, Python, there is no pointer concept, so you can use the available library, but to understand how to install it, you can see your C++ sample code.

Implement a singly linked list. Example for C++: Node declaration:

struct Node {
	  int data;
	  Node* next;
};

Create a new Node:

Node* createNode(int x) {
    Node* temp = new Node;
    temp->next = NULL;
    temp->data = x;
    return temp;
}

Add an element to the end of the listLinker knowing the pointer is pointing to the last element:

Node* addElement(Node*p, int x) {
	Node* temp = createNode(x); // Create a new node with x is the value.
	p->next = temp; // Add that node to the end of the list.
	return temp; // temp now is the lst node.
}

Traversing through the elements in the linked list.

Node* p = l;
while (p != NULL) {
    p = p->next;
}

To be continued... Go back Home.