Lists in c++

Back

Go ahead

Содержание:

Theory
Labs and tasks

Theory

Forward_list or singly-linked lists

Sequence

Elements in sequence containers are ordered in a strict linear sequence. Individual elements are accessed by their position in this sequence.

Linked list

Each element keeps information on how to locate the next element, allowing constant time insert and erase operations after a specific element (even of entire ranges), but no direct random access.

How to create?

List node class:

template <typename T>
struct node
{
  T data;
  node<T>* next;
  node(T data, node<T>* next)
  {
    this->data = data;
    this->next = next;
  }
};

Creating a singly-linked list

Пустой список:

node<int>* p = null;

Adding an item to the top of the list:

p = new node<int>(5,p);

the new operation allocates dynamic memory to a single node

after allocating dynamic memory, the constructor is called with the specified parameters

Example:

p = new node<int>(3,p);

Function templates with lists

Example add_first function template:

template <typename T>
void add_first(T data, node<T>*& p)
{
  p = new node<T>(data,p);
}
int main()
{
  node<int>* p = nullptr;
  add_first(5,p); // two stages of compiling a function template
  add_first(3,p);
}

Creating and Printing a singly-linked (forward) list:

template <typename T>
void print(node<T>* p)
{
  while (p)
  {
    cout << p-> data;
    p = p->next;
  }
}
int main()
{
  node<int>* p = nullptr;
  add_first(5,p);
  add_first(3,p);
  print(p);
}

Freeing the memory occupied by a singly linked list

template <typename T>
void free(node<T>* p)
{
  while (p)
  {
    auto p1 = p;
    p = p->next;
    delete p1;
  }
}
int main()
{
  node<int>* p = nullptr;
  add_first(5,p);
  add_first(3,p);
  print(p);
  //free(p);
  //p = nullptr;
}

Complicated:

Construct forward_list object

// forward_list constructors
#include <iostream>
#include <forward_list>
 
int main ()
{
 
  std::forward_list<int> first;                      // (1) default: empty
  std::forward_list<int> second (3,77);              // (2) fill: 3 seventy-sevens
  std::forward_list<int> third (second.begin(), second.end()); // (3) range initialization
  std::forward_list<int> fourth (third);            // (4) copy constructor
  std::forward_list<int> fifth (std::move(fourth));  // (5) move ctor. (fourth wasted)
  std::forward_list<int> sixth = {3, 52, 25, 90};    // (6) initializer_list constructor
 
  std::cout << "first:" ; for (int& x: first)  std::cout << " " << x; std::cout << '\n';
  std::cout << "second:"; for (int& x: second) std::cout << " " << x; std::cout << '\n';
  std::cout << "third:";  for (int& x: third)  std::cout << " " << x; std::cout << '\n';
  std::cout << "fourth:"; for (int& x: fourth) std::cout << " " << x; std::cout << '\n';
  std::cout << "fifth:";  for (int& x: fifth)  std::cout << " " << x; std::cout << '\n';
  std::cout << "sixth:";  for (int& x: sixth)  std::cout << " " << x; std::cout << '\n';
 
  return 0;
}

Expected output:

first:
second: 77 77 77
third: 77 77 77
fourth:
fifth: 77 77 77
sixth: 3 52 25 90

(1) — default — Constructs an empty container, with no elements.
(2) — fill constructor — Constructs a container with n elements. Each element is a copy of val (if provided).
(3) — range constructor — Constructs a container with as many elements as the range [first,last), with each element emplace-constructed from its corresponding element in that range, in the same order.
(4) — copy constructor (and copying with allocator) — Constructs a container with a copy of each of the elements in fwdlst, in the same order.
(5) — move constructor (and moving with allocator) — Constructs a container that acquires the elements of fwdlst. If alloc is specified and is different from fwdlst‘s allocator, the elements are moved. Otherwise, no elements are constructed (their ownership is directly transferred). fwdlst is left in an unspecified but valid state.
(6) — initializer list constructor — Constructs a container with a copy of each of the elements in il, in the same order.

Forward_list::assign

Syntax:
range (1)

template 
void assign (InputIterator first, InputIterator last);

fill (2)

void assign (size_type n, const value_type& val);

initializer list (3)

void assign (initializer_list il);

In the range version (1), the new contents are elements constructed from each of the elements in the range between first and last, in the same order.

In the fill version (2), the new contents are n elements, each initialized to a copy of val.

In the initializer list version (3), the new contents are copies of the values passed as initializer list, in the same order.

Any elements held in the container before the call are destroyed and replaced by newly constructed elements (no assignments of elements take place).
Parameters:
first, last
Input iterators to the initial and final positions in a sequence. The range used is [first,last), which includes all the elements between first and last, including the element pointed by first but not the element pointed by last.
The function template argument InputIterator shall be an input iterator type that points to elements of a type from which value_type objects can be constructed.
n
New size for the container.
Member type size_type is an unsigned integral type.
val
Value to fill the container with. Each of the n elements in the container will be initialized to a copy of this value.
Member type value_type is the type of the elements in the container, defined in forward_list as an alias of its first template parameter (T).
il
An initializer_list object. The compiler will automatically construct such objects from initializer list declarators. Member type value_type is the type of the elements in the container, defined in forward_list as an alias of its first template parameter (T).
Example:

#include <iostream>
#include <forward_list>
 
int main ()
{
  std::forward_list<int> first;
  std::forward_list<int> second;
 
  first.assign (4,15);                           // 15 15 15 15
 
  second.assign (first.begin(),first.end());     // 15 15 15 15
 
  first.assign ( {77, 2, 16} );                  // 77 2 16
 
  std::cout << "first contains: ";
  for (int& x : first) std::cout << ' ' << x;
  std::cout << '\n';
 
  std::cout << "second contains: ";
  for (int& x : second) std::cout << ' ' << x;
  std::cout << '\n';
 
  return 0;
}

Output:

first contains: 77 2 16
second contains: 15 15 15 15

Assignment operator = with forward_list

Syntax:
copy (1)

forward_list& operator= (const forward_list& fwdlst);

move (2)

forward_list& operator= (forward_list&& fwdlst);

initializer list(3)

forward_list& operator= (initializer_list il);

Assigns new contents to the container, replacing its current contents.

The copy assignment (1) copies all the elements from fwdlst into the container (with fwdlst preserving its contents).

The move assignment (2) moves the elements of fwdlst into the container (x is left in an unspecified but valid state).

The initializer list assignment (3) copies the elements of il into the container.

The container preserves its current allocator, except if the allocator traits indicate fwdlst’s allocator should propagate. This allocator is used (through its traits) to allocate or deallocate if there are changes in storage requirements, and to construct or destroy elements, if needed.
Parameters:
fwdlst
A forward_list object of the same type (i.e., with the same template parameters, T and Alloc).
il
An initializer_list object. The compiler will automatically construct such objects from initializer list declarators. Member type value_type is the type of the elements in the container, defined in forward_list as an alias of its first template parameter (T).
Example:

#include <iostream>
#include <forward_list>
 
template<class Container>
Container by_two (const Container& x) {
  Container temp(x); 
  for (auto& x:temp) 
      x*=2;
  return temp;
}
 
int main ()
{
  std::forward_list<int> first (4);      // 4 ints
  std::forward_list<int> second (3,5);   // 3 ints with value 5
 
  first = second;                        // copy assignment
  second = by_two(first);                // move assignment
 
  std::cout << "first: ";
  for (int& x : first) std::cout << ' ' << x;
  std::cout << '\n';
 
  std::cout << "second: ";
  for (int& x : second) std::cout << ' ' << x;
  std::cout << '\n';
 
  return 0;
}

In the first assignment, second is an lvalue: the copy assignment function is called.
In the second assignment, the value returned by by_two(first) is an rvalue: the move assignment function is called.
Output:

first: 5 5 5
second: 10 10 10

resize () function

void resize (size_type n);
void resize (size_type n, const value_type& val);

Resizes the container to contain n elements.
If n is smaller than the current number of elements in the container, the content is trimmed to contain only its first n elements, removing those beyonf (and destroying them).
If n is greater than the current number of elements in the container, the content is expanded by inserting at the end as many elements as needed to reach a size of n elements. If val is specified, the new elements are initialized as copies of val, otherwise, they are value-initialized.
Example

// resizing forward_list
#include <iostream>
#include <forward_list>
 
int main ()
{
  std::forward_list<int> mylist = {10, 20, 30, 40, 50};
                                // 10 20 30 40 50
  mylist.resize(3);             // 10 20 30
  mylist.resize(5,100);         // 10 20 30 100 100
 
  std::cout << "mylist contains:";
  for (int& x: mylist) std::cout << ' ' << x;
  std::cout << '\n';
 
  return 0;
}

mylist contains: 10 20 30 100 100

insert_after function

Example

// forward_list::insert_after
#include <iostream>
#include <array>
#include <forward_list>
 
int main ()
{
  std::array<int,3> myarray = { 11, 22, 33 };
  std::forward_list<int> mylist;
  std::forward_list<int>::iterator it;
 
  it = mylist.insert_after ( mylist.before_begin(), 10 );          // 10
                                                                   //  ^  <- it
  it = mylist.insert_after ( it, 2, 20 );                          // 10 20 20
                                                                   //        ^
  it = mylist.insert_after ( it, myarray.begin(), myarray.end() ); // 10 20 20 11 22 33
                                                                   //                 ^
  it = mylist.begin();                                             //  ^
  it = mylist.insert_after ( it, {1,2,3} );                        // 10 1 2 3 20 20 11 22 33
                                                                   //        ^
 
  std::cout << "mylist contains:";
  for (int& x: mylist) std::cout << ' ' << x;
  std::cout << '\n';
  return 0;
}

Output:

mylist contains: 10 1 2 3 20 20 11 22 33

Doubly linked lists

Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.

template < class T, class Alloc = allocator > class list;

List containers are implemented as doubly-linked lists.
Doubly linked lists can store each of the elements they contain in different and unrelated storage locations. The ordering is kept internally by the association to each element of a link to the element preceding it and a link to the element following it.
Doubly linked list keeps two links per element: one pointing to the next element and one to the preceding one, allowing efficient iteration in both directions, but consuming additional storage per element and with a slight higher time overhead inserting and removing elements.
Compared to other base standard sequence containers (array, vector and deque), forward_list perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

* Information has taken from: http://www.cplusplus.com/reference/forward_list/forward_list/.

Labs and tasks

Lab 1: Creating Linked Lists
To do: Create a linked lists with three elements (nodes) named root, first and second. Create a function to print the elements of the list.

Expected output:

Lab 0
1 2 3

✍ How to do:

Create an empty console application. Add the source file and open its code. Include all the necessary libraries and main function.
First of all, let’s create a linkled list. It can be done as a structure above the main function:

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

data is to store a value of the element, and *next is a pointer to point at the memory address of the next list element.

In the main function, three linked lists must be declared:

LinkedList *root, *second, *third;

root = new LinkedList;
second = new LinkedList;
third = new LinkedList;

After we’ve declared lists, let’s assign the values:

root->data = 1;
root->next = second;

second->data = 2;
second->next = third;

third->data = 3;
third ->next = NULL;

data is a value of the element, while next is a stored address to the next element.

Now, let’s create a function to print out the values of the list. It will have an argument — a pointer to the root element. Add the following code above the main function:

void printLinkedList(LinkedList*root) {
	while (root)
	{
		printf("%d ", root->data);
		root = root->next;
	}
}

We use the while loop to iterate over the list’s nodes. Each iteration we assign the address of the next element to the root. The value of the next of the last element equals to 0 (NULL), thus the while loop will stop.

Call this function inside the main function:

printLinkedList(root);

Run the application and check the output.

Lab 2: Circular lists:
To do: Create a circular list with three nodes. Assign values for nodes and print them out.

Expected output:

List contains the following nodes:
1 2 3

✍ How to do:

Create an empty console application. Add the source file and open its code. Include all the necessary libraries and main function.
First of all, let’s create a structure which represents a node. It can be done above the main function:

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

Now, we’re going to сreate a function to add the first node to the list. This means the list is empty. The function will take two arguments: an address of node to create and the data to store it in node being created. Add the signature of the function above the main:

struct Node *addToEmpty(struct Node *last, int data) 
{
	// ...
};

Inside this function it is better to check if the list is really empty. If it is not, we should return the address of the created node to work them inside another function.

if (last != NULL) return last;

Then, we need to allocate a dynamic memory for a new node. Let’s call this node temp:

struct Node * temp = new Node;

Now, we must assign data value and address value to the node. We have to do it to make the list circular:

temp->data = data; // we assign passed data to the node
last = temp; // since we have no anything inside list, so last node will be the only one
last->next = last; // this line makes link circular; the node actually points to itself (because the only one)
return last;

Now, we’re going to сreate a function to add the node to the list, which is not empty. The function will take two arguments: an address of node to create and the data to store it in node being created. Add the signature of the function above the main:

struct Node *addEnd(struct Node *last, int data)
{
  // ...
}

Inside this function it is better to check if the list is empty. If it is, we should return the calling of addToEmpty function:

if (last == NULL) 
		return addToEmpty(last,data);

If the function is not empty, we need to allocate a dynamic memory for a new node:

struct Node * temp = new Node;

After, we must assign data value and address value to the node. We have to do it to make the list circular:

temp->data = data;
temp->next = last->next; // the address of the previous node is assigned 
last->next = temp; // assign the address of the current node to the previous node
last = temp;
return last;

Now we’re going to create a function to traverse the list. It will have single argument — a pointer to the list to be traversed. Add the signeture begore main:

void traverse(struct Node *first)
{
  //...
}

Inside the function we should create a pointer to the list:

struct Node *tmp = first;

After, we’re going to loop over the list nodes and print them out:

if (first != NULL) {
		do
		{
			cout << tmp->data << " ";
			tmp = tmp->next; // move to the next node
		} while (tmp != first);
	}

Now, we can turn to the main function and create the future list. The NULL must be assigned to it (it is empty).

struct Node *last = NULL;

To add the first node we should call the addToEmpty() function, since it is empty. To create the second and third nodes we should call the addEnd() function. The values must be 1, 2 and 3:

last = addToEmpty(last, 1); // data = 1
last = addEnd(last, 2);
last = addEnd(last, 3);

At last, we must call the function to print the nodes out:

cout << "List contains the following nodes:" << endl;
traverse(last->next);

Run the application and check the output.

Lab 3: Forward lists: Using list methods
To do: Create a solution to test the methods of a list type. Create three lists and use the following methods with them:

insert_after
emplace_after
reverse
splice
sort
merge
remove
remove_if

Expected output:

Lab 3
list 1: 5 4 3 2
 list 2: 1 4 7 6
 list 3: 9 8 7
 1. insert_after method, list1 (insert 8 number in the position 2):
5 8 4 3 2
 2. emplace_after method, list3 (add 5 to list3 in the position 2):
9 5 8 7
 3. reversed method(list1):
2 3 4 8 5
 4. splice method (list1 with list3):
 after splice, list1:
2 9 5 8 7 3 4 8 5
 after splice, list 3:

 5. sort method, list 1:
2 3 4 5 5 7 8 8 9
 sort method, list 2:
1 4 6 7
 6. merged method (list1 and list2):
1 2 3 4 4 5 5 6 7 7 8 8 9
 7. remove method, list1 (2 is removed):
1 3 4 4 5 5 6 7 7 8 8 9
 8. remove_if method, list1 (numbers>4 are removed):
1 3 4 4

✍ How to do:

To perform the lab, create an empty console application with a name Lesson12. Add file: L12Lab3main.cpp.

Include all the necessary libraries.

Create int main function that returns 0.

In the main function declare three lists, initialize them with values and print them out to the console:

#include <forward_list> 
//...
forward_list<int> list1 = { 5,4,3,2 };
forward_list<int> list2 = { 1,4,7,6 };
forward_list<int> list3 = { 9,8,7 };
cout << "\n list 1: ";
for (auto &elem : list1)
  cout << elem << " ";
cout << "\n list 2: ";
for (auto &elem : list2)
  cout << elem << " ";
cout << "\n list 3: ";
for (auto &elem : list3)
  cout << elem << " ";

Test the following functions and consider results:

insert_after method

Insert 8 into 2 position of list1:

cout << "\n 1. insert_after function, list1 (insert 8 number in the position 2):" << endl;
list1.insert_after(list1.begin(), 8);
for (auto &elem : list1)
	cout << elem << " ";

emplace_after

Insert 5 into 2 position of list3:

cout << "\n 2. emplace_after function, list3 (add 5 to list3 in the position 2):" << endl;
list3.emplace_after(list3.begin(), 5);
for (auto &elem : list3)
	cout << elem << " ";

reverse

Reverse list1 by yourself and output the result.

splice_after:

You should splice list3 from the position 2 of list2

list1.splice_after(list1.begin(), list3);
cout << "\n 4. splice function (list1 with list3):" << endl;
cout << "\n after splice, list1:" << endl;
for (auto &elem : list1)
  cout << elem << " "; 
cout << "\n after splice, list 3:" << endl;
for (auto &elem : list3)
  cout  << elem << " "; //must become empty

sort

Sort list1 and list2 by yourself and output the results.

merge:

Merge list1 and list2. Note that lists must be sorted:

list1.merge(list2);
cout << "\n 6. merged function (list1 and list2):" << endl;
for (auto &elem : list1)
   cout << elem << " ";

remove

Remove 2 from the list1:

list1.remove(2);
cout << "\n 7. remove function, list1 (2 is removed):" << endl;
for (auto &elem : list1)
  cout << elem << " ";

remove_if

Remove all the elements which are greater than 4 from the list1:

list1.remove_if([](int n) {
	return n > 4;
});
cout << "\n 8. remove_if function, list1 (numbers>4 are removed):" << endl;
for (auto &elem : list1)
  cout << elem << " ";

Run the program.

Back

Go ahead