Linked List Implementation in C++ | Techie Delight (2023)

This post provides an overview of some available techniques to implement a linked list in C++ programming language.

We know that each node of a linked list contains a single data field and a pointer to the next node in the list.

1

2

3

4

5

6

7

// A Linked List Node

class Node

{

public:

int key;// data field

Node* next; // pointer to the next node

};


The nodes of the linked list are allocated in the heap memory. We can use the new operator in C++ for dynamic memory allocation and the delete operator to deallocate the allocated memory.

1

2

3

4

5

6

7

8

9

10

11

12

// Utility function to return new linked list node from the heap

Node* newNode(int key)

{

// allocate the new node in a heap using the new operator and set its data

Node* node = new Node;

node->key = key;

// set the `.next` pointer of the new node to point to null

node->next = nullptr;

return node;

}

Practice this problem


There are several methods to construct a singly linked list. Each is covered in detail below:

1. Naive method

A simple solution would be to allocate memory for all individual nodes of the linked list, set their data, and rearrange their pointers to build the complete list.

Linked List Implementation in C++ | Techie Delight (1)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

#include <iostream>

using namespace std;

// A Linked List Node

class Node

{

public:

int key;// data field

Node* next; // pointer to the next node

};

// Utility function to return new linked list node from the heap

Node* newNode(int key)

{

// allocate a new node in a heap and set its data

Node* node = new Node;

node->key = key;

// `.next` pointer of the new node points to nothing

node->next = nullptr;

return node;

}

// Function for linked list implementation containing three nodes

Node* constructList()

{

// construct three linked list nodes

Node* first = newNode(1);

Node* second = newNode(2);

Node* third = newNode(3);

// rearrange the pointers to construct a list

Node* head = first;

first->next = second;

second->next = third;

// return a pointer to the first node in the list

return head;

}

// Helper function to print a linked list

void printList(Node* head)

{

Node* ptr = head;

while (ptr)

{

cout << ptr->key << " -> ";

ptr = ptr->next;

}

cout << "nullptr";

}

int main()

{

// `head` points to the first node (also known as a head node) of a linked list

Node *head = constructList();

// print linked list

printList(head);

return 0;

}

DownloadRun Code

2. Single Line

We can write the above code in a single line by passing the next node as an argument to the newNode() function:

Linked List Implementation in C++ | Techie Delight (2)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

#include <iostream>

using namespace std;

// A Linked List Node

class Node

{

public:

int key;// data field

Node* next; // pointer to the next node

};

// Utility function to return new linked list node from the heap

Node* newNode(int key, Node* next)

{

// allocate a new node in a heap and set its data

Node* node = new Node;

node->key = key;

// set the `.next` pointer of the new node to point to the current

// first node of the list.

node->next = next;

return node;

}

// Function for linked list implementation containing three nodes

Node* constructList()

{

Node* head = newNode(1, newNode(2, newNode(3, nullptr)));

return head;

}

// Helper function to print a linked list

void printList(Node* head)

{

Node* ptr = head;

while (ptr)

{

cout << ptr->key << " -> ";

ptr = ptr->next;

}

cout << "nullptr";

}

int main()

{

// `head` points to the first node (also known as a head node) of a linked list

Node *head = constructList();

// print linked list

printList(head);

return 0;

}

DownloadRun Code

3. Generic Method

Both above methods are not practical when the total number of nodes increases in the linked list. If the keys are given in any container, such as an array, vector, or set, we can easily construct a linked list by traversing the container, as shown below:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

#include <iostream>

#include <vector>

using namespace std;

// A Linked List Node

class Node

{

public:

int key;// data field

Node* next; // pointer to the next node

};

// Utility function to return new linked list node from the heap

Node* newNode(int key, Node* next)

{

// allocate a new node in a heap and set its data

Node* node = new Node;

node->key = key;

// set the `.next` pointer of the new node to point to the current

// first node of the list.

node->next = next;

return node;

}

// Function for linked list implementation from a given set of keys

Node* constructList(vector<int> const &keys)

{

Node* head, *node = nullptr;

// start from the end of the array

for (int i = keys.size() - 1; i >= 0; i--)

{

node = newNode(keys[i], node);

head = node;

}

return head;

}

// Helper function to print a linked list

void printList(Node* head)

{

Node* ptr = head;

while (ptr)

{

cout << ptr->key << " -> ";

ptr = ptr->next;

}

cout << "nullptr";

}

int main()

{

// input keys (in reverse order)

vector<int> keys = { 4, 3, 2, 1 };

// construct linked list

Node *head = constructList(keys);

// print linked list

printList(head);

return 0;

}

DownloadRun Code

4. Standard Solution

The standard solution adds a single node to the head end of any list. This function is called push() since we are adding the link to the head end, making a list look a bit like a stack.

We know that C++ has its built-in & argument feature to implement reference parameters. If we append an & to the type of parameter, the compiler will automatically make the parameter operate by reference without disturbing the argument’s type.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

#include <iostream>

#include <vector>

using namespace std;

// A Linked List Node

class Node

{

public:

int key;// data field

Node* next; // pointer to the next node

};

/*

push() in C++ — we just add `&` to the right-hand side of the head

parameter type, and the compiler makes that parameter work by reference.

So, this code changes the caller's memory, but no extra uses of `*` are

necessary — we access "head" directly, and the compiler makes that

change reference back to the caller.

*/

void push(Node* &headRef, int key)

{

// allocate a new node in a heap and set its data

Node* node = new Node;

node->key = key;

// set the `.next` pointer of the new node to point to the current

// first node of the list.

// no extra use of `*` necessary on the head — the compiler

// takes care of it behind the scenes

node->next = headRef;

// change the head pointer to point to the new node, so it is

// now the first node in the list.

headRef = node;

}

// Function for linked list implementation from a given set of keys

Node* constructList(vector<int> const &keys)

{

Node* head = nullptr;

// start from the end of the array

for (int i = keys.size() - 1; i >= 0; i--)

{

// Note that no extra use `&` necessary — the compiler takes

// care of it here too. These calls are changing the head.

push(head, keys[i]);

}

return head;

}

// Helper function to print a linked list

void printList(Node* head)

{

Node* ptr = head;

while (ptr)

{

cout << ptr->key << " -> ";

ptr = ptr->next;

}

cout << "nullptr";

}

int main()

{

// input keys (in reverse order)

vector<int> keys = { 4, 3, 2, 1 };

// construct linked list

Node *head = constructList(keys);

// print linked list

printList(head);

return 0;

}

DownloadRun Code

5. Make head pointer global

We can construct a linked list by making the head pointer global, but this approach is not recommended since global variables are usually considered bad practice.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

#include <iostream>

#include <vector>

using namespace std;

// A Linked List Node

class Node

{

public:

int key;

Node* next;

};

// Global head pointer

Node* head = nullptr;

// Takes a list and a data value, creates a new link with the given

// data and pushes it onto the list's front.

void push(int key)

{

// allocate a new node in a heap and set its data

Node* node = new Node;

node->key = key;

// set the `.next` pointer of the new node to point to the current

// head node of the list.

node->next = head;

// change the head pointer to point to the new node, so it is

// now the first node in the list.

head = node;

}

// Function for linked list implementation from a given set of keys

void constructList(vector<int> const &keys)

{

// start from the end of the array

for (int i = keys.size() - 1; i >= 0; i--) {

push(keys[i]);

}

}

// Helper function to print the global linked list `head`

void printList()

{

Node* ptr = head;

while (ptr)

{

cout << ptr->key << " -> ";

ptr = ptr->next;

}

cout << "nullptr";

}

int main()

{

// input keys (in reverse order)

vector<int> keys = { 4, 3, 2, 1 };

// construct linked list

constructList(keys);

// print linked list

printList();

return 0;

}

DownloadRun Code

6. Return head from the push() function

Another common approach many programmers follow is to return the head node from the push() function and update the head in the caller. This is demonstrated below:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

#include <iostream>

#include <vector>

using namespace std;

// A Linked List Node

class Node

{

public:

int key;// data field

Node* next; // pointer to the next node

};

/*

Takes a list and a data value, creates a new link with the given data

and pushes it onto the list's front.

*/

Node* push(Node* head, int key)

{

// allocate a new node in a heap and set its data

Node* node = new Node;

node->key = key;

// set the `.next` pointer of the new node to point to the current

// first node of the list.

node->next = head;

// return the new node, so it becomes the first node in the list

return node;

}

// Function for linked list implementation from a given set of keys

Node* constructList(vector<int> const &keys)

{

Node* head = nullptr;

// start from the end of the array

for (int i = keys.size() - 1; i >= 0; i--) {

head = push(head, keys[i]);// update head here

}

return head;

}

// Helper function to print a linked list

void printList(Node* head)

{

Node* ptr = head;

while (ptr)

{

cout << ptr->key << " -> ";

ptr = ptr->next;

}

cout << "nullptr";

}

int main()

{

// input keys (in reverse order)

vector<int> keys = { 4, 3, 2, 1 };

// construct linked list

Node *head = constructList(keys);

// print linked list

printList(head);

return 0;

}

DownloadRun Code


Continue Reading:

Linked List – Insertion at Tail | C, Java, and Python Implementation


Also See:

Linked List Implementation in C

Linked List Implementation in Java

Linked List Implementation in Python


References: http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

Top Articles
Latest Posts
Article information

Author: Jerrold Considine

Last Updated: 01/24/2023

Views: 6493

Rating: 4.8 / 5 (78 voted)

Reviews: 85% of readers found this page helpful

Author information

Name: Jerrold Considine

Birthday: 1993-11-03

Address: Suite 447 3463 Marybelle Circles, New Marlin, AL 20765

Phone: +5816749283868

Job: Sales Executive

Hobby: Air sports, Sand art, Electronics, LARPing, Baseball, Book restoration, Puzzles

Introduction: My name is Jerrold Considine, I am a combative, cheerful, encouraging, happy, enthusiastic, funny, kind person who loves writing and wants to share my knowledge and understanding with you.