How do you write a linked list insertion and deletion implementation in c plus plus?

Answer 1

There is no single container that is ideally suited to every task, therefore the container you choose is often a compromise, depending upon which operations you need to perform the most.

Linked lists are ideally suited to applications where a lot of insertions need to occur within the middle of the list. The downside is that you must first traverse the list from the first or last element in order to reach the insertion point; there is no constant time random access. Thus the average search time is O(n/4) for a list of n elements. For a forward list, search times increase to O(n/2).

Traversing an array has a similar complexity, but because array elements occupy contiguous memory, they are actually quicker to traverse. And if the array is also sorted, traversal becomes O(n log n) by taking advantage of binary search traversal (recursively starting at the middle element and discounting one half of the array on each recursion). However, arrays are suited to insertions at the end of the array only. This is achieved by reserving more memory than is actually needed, but when that reserve runs out, the entire array has to be reallocated, which can result in every element being copied to new memory.

Lists are not ideally suited to sorting algorithms other than those solely reliant upon sequential access (such as merge sort). However, it can still be quicker to copy the list to an array, sort the array, and then reconstruct the list from the sorted array.

Ultimately no-one can tell you which is the best container to use in any given situation. Never assume that just because a container is ideally suited to a specific task that it is ideal for all the tasks you actually need to perform. Always measure the performance and try other containers to see which works best overall.

As a rule of thumb, consider the vector as your default option. Measure the performance using high-resolution timers, then try an alternative container.

Answer 2

#include<iostream>

#include<list>

#include<algorithm>

void print_list (const std::list<int>& list)

{

for (auto i : list)

std::cout << i << '\t';

std::cout << std::endl;

}

int main()

{

// initialise a linked list.

std::list<int> list {0,1,2,3,4,5,6,7,8,9};

print_list (list);

// traverse to the node with value 4.

std::list<int>::iterator i = std::find (list.begin(), list.end(), 4);

// insert the value 42 in front of this node.

list.insert (i, 42);

print_list (list);

// remove the value 4.

list.remove (4);

print_list (list);

}

Answer 3

The standard template library (STL) includes a ready-made linked list in std::list. The following example creates a linked list with 10 random integers and then prints the list in both forward and reverse order.

#include<iostream>

#include<list>

#include<time.h>

int main()

{

srand((unsigned)time(NULL));

std::list<int> linked_list;

for(int i=0; i<10; ++i)

linked_list.push_back(rand());

for(std::list<int>::iterator i=linked_list.begin(); i!=linked_list.end(); ++i)

std::cout<<*(*i)<<" ";

std::cout<<std::endl;

for(std::list<int>::reverse_iterator i=linked_list.rbegin(); i!=linked_list.rend(); ++i)

std::cout<<*(*i)<<" ";

std::cout<<std::endl;

}

Answer 4

The simple answer is to use the std::list template from the standard template library. If you need more specific behaviour, you can either derive a new class from the template or embed the template as a member object in your class.

However, it is important to note that the standard template library and similar toolkits do not guarantee a specific implementation; they guarantee a specific behavior. Nothing says, for example, that std::list must be implemented as a linked list. However, the promise is given that std::list behaves like a linked list: it can grow (or shrink) dynamically, it can be sorted, and it has constant insertion.

Answer 5

A linked list is a collection of data elements. Unlike an array where the data elements are allocated in contiguous memory, the data elements of a linked list are allocated non-contiguously. In order to traverse from one data element to the next, each element is stored in a node where each node points to the next node in the sequence. For example, a linked list of integers would use the following node structure:

typedef struct Node_t {

int data;

Node* next;

} Node;

In order to maintain a list of nodes, we need only keep track of the head node (the first node in the list). We achieve this through another structure:

typedef struct List_t {

Node* head;

} List;

Initially, the head node is a null pointer.

The two primary functions of a list are push_back and pop_back. While a push_back implies we add new data to the end of the list, we actually insert at the head of the list such that the new node becomes the head node. This is because the head node is the only node we have constant time access to and is therefore the most efficient method of inserting new nodes. The push_back method is implemented as follows:

void push_back (List* list, int data) {

if (!list) return;

Node* node = malloc (sizeof(Node));

node.data = data;

node.next = list.head;

list.head = node;

}

Similarly, the pop_back method is implemented as follows:

void pop_back (List* list) { if (!list !list.head) return;

Node* node = list.head;

list.head = node.next;

free (node);

}

You will note that a linked list has the same functionality as a stack, where the head node is the top of the stack. However, a linked list usually includes additional methods. For instance, it would be useful to search a list to locate the first occurrence of a particular value, returning the node holding that value:

Node* find (List* list, int data) {

if (!list) return 0;

Node* node = list.head;

while (node && node.data!=data) node = node.next;

return node;

}

This function will return 0 (a null pointer) if the data does not exist.

Having located a node, it would be useful to be able to insert a new node immediately after that node:

Node* insert_after (Node* node, int data) {

if (!node) return 0;

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

new_node.data = data;

new_node.next = node.next;

node.next = new_node;

return new_node;

}

Finally, it would also be useful to remove a node from somewhere other than the head of the list:

void remove (List* list, int data) {

if (!list) return;

Node* node = list.head;

while (node && node.next && node.next.data!=data) node = node.next;

if (!node !node.next) return;

node.next = node.next.next;

free (node.next);

}

This is the minimum functionality we need for a linked list. However, we can add other functions such a counter to count the number of elements in a list:

unsigned count (List* list) {

unsigned count = 0;

if (!list) return count;

Node* node = list.head;

while (node) {

++count;

node=node.next;

}

return count;

}