Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Like an array, a linked list is a linear data structure. Unlike arrays, linked list elements are not stored in contiguous locations; The element uses pointer links.

Why do you choose linked lists?

Arrays can be used to store similar types of linear data, but arrays have the following limitations. 1) The size of the array is fixed: so we must know the upper limit of the number of elements in advance. In addition, in general, the allocated memory is equal to the upper limit regardless of usage. 2) Inserting a new element into an array of elements is expensive because the room must be created for the new element and the existing element must be moved to create the room.

For example, in a system, if we maintain a sorted list of ids in the array ID []. Id [] = [1000, 1010, 1050, 2000, 2040]

If we were to insert a new ID 1005, we would have to move all elements after 1000 (excluding 1000) in order to preserve the sorting order.

Deleting an array is also expensive unless you use some special techniques. For example, to remove 1010 in ID [], you must move everything after 1010.

Is better than that of array

1) Dynamic size 2) easy to insert/remove

disadvantages

1) Random access is not allowed. We must access the elements sequentially, starting with the first node. So we can’t use its default implementation to effectively perform binary search on linked lists. 2) Each element of the list requires additional pointer storage. 3) Not cache friendly. Because array elements are contiguous positions, there is locality of references, which is not present in the case of linked lists.

said

A linked list is represented by a pointer to the first node of the list. The first node is called the header. If the list is empty, the header value is NULL. Each node in the list consists of at least two parts:

  1. data
  2. A pointer (or reference) to the next node

In C, we can use structures to represent a node. Here is an example of a linked list node with integer data. In Java or C#, LinkedList can be represented as a class, while a Node can be represented as a separate class. The LinkedList class contains a reference to the Node class type.

This is a simple linked list in C++

class Node {
public:
	int data;
	Node* next;
};
Copy the code

Let’s create a simple linked list with three nodes.

// A simple CPP program to introduce linked lists
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
	int data;
	Node* next;
};

// Create a simple linked list with 3 nodes
int main(a)
{
	Node* head = NULL;
	Node* second = NULL;
	Node* third = NULL;

	// Allocate 3 nodes in the heap
	head = new Node(a); second =new Node(a); third =new Node(a);/* Three blocks have been allocated dynamically. We have a pointer to the three pieces as the head, the second and third head second third | | | | | | + - + - + + - + - + + - + - + # # | | | | | | # # # # | | | + - + - + + - + - + + - + - + # for any random value. The data is random because we haven't allocated anything yet */

	head->data = 1; // Allocate data on the first node
	head->next = second; // Link the first node to the second node

	/* Data has been allocated to the data part of the first block (the header). The next pointer to the first block points to the second. So they're all linked. head second third | | | | | | +---+---+ +----+----+ +-----+----+ | 1 | o----->| # | # | | # | # | +---+---+ +----+----+ + -- -- -- -- - + - + * /

	// Assign data to the second node
	second->data = 2;

	// Connect the second node to the third node
	second->next = third;

	/* The data portion of the second block to which data has been allocated (the block pointed by seconds). The next pointer to the second block points to the third block. So all three blocks are linked. head second third | | | | | | +---+---+ +---+---+ +----+----+ | 1 | o----->| 2 | o-----> | # | # | +---+---+ +---+---+ + - + - + * /

	third->data = 3; // Assign data to the third node
	third->next = NULL;

	/* The part of the data that has been allocated to the third block (the block pointed to by the third). The next pointer to the third block is NULL, indicating that the list terminates here. We've got the linked list ready. head | | +---+---+ +---+---+ +----+------+ | 1 | o----->| 2 | o-----> | 3 | NULL | +---+---+ +---+---+ +----+------+ Note that only the header is sufficient to represent the entire list. We can traverse the list by following the next pointer. * /

	return 0;
}
Copy the code

List traversal

In the previous program, we created a simple linked list with three nodes. Let’s walk through the created list and print the data for each node. For traversal, let’s write a generic function printList() to print any given list.

// a simple C++ program for traversing lists
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
	int data;
	Node* next;
};

// This function prints the contents of the list starting at the given node
void printList(Node* n)
{
	while(n ! =NULL) {
		cout << n->data << ""; n = n->next; }}// Driver code
int main(a)
{
	Node* head = NULL;
	Node* second = NULL;
	Node* third = NULL;

	// Allocate 3 nodes in the heap
	head = new Node(a); second =new Node(a); third =new Node(a); head->data =1; // Allocate data on the first node
	head->next = second; // Connect the first node to the second node

	second->data = 2; // Assign data to the second node
	second->next = third;

	third->data = 3; // Assign data to the third node
	third->next = NULL;

	printList(head);

	return 0;
}
Copy the code

Output:

 1 2 3
Copy the code

🛬 wuhu! Take off!

I’ve been writing tech blogs for a long time, mostly through Nuggets, and this is my tutorial on singly linked lists of data structures. I like to share technology and happiness through articles. You can visit my blog at juejin.cn/user/204034… For more information. Hope you like it! 😊

🥇 past quality articles

❤️ Single-player AI minesweeper using Python ❤️ [Python Introduction Project] Generate qr codes using Python ❤️ Simple analog clock ❤️ using HTML, CSS and JavaScript Make a random password generator ❤️ Make a great weather Web application using HTML, CSS, JS and API ❤️ Are you really proficient with HTML5 and how many of these 10 cool H5 features do you know? ❤️ how to design a Neumorphism style digital clock in JavaScript

📣 Endnote: For more information on data structures, you can follow me: Haiyong, I hope you found this article helpful.

If you see this, thank you for reading 🙂

💌 welcomes your comments and suggestions in the comments section! 💌

If you really learn something new from this article, like it, bookmark it and share it with your friends. 🤗 and finally, don’t forget ❤ or 📑.