xtd::collections::generic::linked_list< type_t, allocator_t > Class Template Reference

Inheritance diagram for xtd::collections::generic::linked_list< type_t, allocator_t >:

Definition

template<typename type_t, typename allocator_t>
class xtd::collections::generic::linked_list< type_t, allocator_t >

Represents a doubly linked list.

Definition

template<typename type_t>
class linked_list : public xtd::object, public xtd::collections::generic::icollection <type_t>;

Header

#include <xtd/collections/generic/linked_list>

Namespace

xtd::collections::generic

Library

xtd.core

Examples

The following code example demonstrates many features of the xtd::collections::generic::linked_list <type_t> class.

#include <xtd/xtd>
 
using namespace text;
 
class example {
public:
  static auto main() -> void {
    // Create the link list.
    auto sentence = linked_list<string> { "the", "fox", "jumps", "over", "the", "dog" };
    display(sentence, "The linked list values:");
    
    // Add the word 'today' to the beginning of the linked list.
    sentence.add_first("today");
    display(sentence, "Test 1: Add 'today' to beginning of the list:");
    
    // Move the first node to be the last node.
    auto node = *sentence.first();
    sentence.remove(node);
    sentence.add_last(node);
    display(sentence, "Test 2: Move first node to be last node:");
    
    // Change the last node to 'yesterday'.
    sentence.remove_last();
    sentence.add_last("yesterday");
    display(sentence, "Test 3: Change the last node to 'yesterday':");
    
    // Move the last node to be the first node.
    node = *sentence.last();
    sentence.remove(node);
    sentence.add_first(node);
    display(sentence, "Test 4: Move last node to be first node:");
    
    // Indicate the last occurence of 'the'.
    sentence.remove_first();
    node = *sentence.find_last("the");
    indicate_node(node, "Test 5: Indicate last occurence of 'the':");
    
    // Add 'lazy' and 'old' after 'the' (the linked_list_node named node).
    sentence.add_after(node, "old");
    sentence.add_after(*sentence.find_last("the"), "lazy");
    indicate_node(*sentence.find_last("the"), "Test 6: Add 'lazy' and 'old' after 'the':");
    
    // Indicate 'fox' node.
    node = *sentence.find_last("fox");
    indicate_node(node, "Test 7: Indicate the 'fox' node:");
    
    // Add 'quick' and 'brown' before 'fox':
    sentence.add_before(*sentence.find("fox"), "quick");
    sentence.add_before(*sentence.find("fox"), "brown");
    indicate_node(*sentence.find("fox"), "Test 8: Add 'quick' and 'brown' before 'fox':");
    
    // Keep a reference to the current node, 'fox', and to the previous node in the list. Indicate the 'dog' node.
    node = *sentence.find_last("dog")->previous();
    indicate_node(*sentence.find("dog"), "Test 9: Indicate the 'dog' node:");
    
    // The add_before method throws an invalid_operation_exception if you try to add a node that already belongs to a list.
    console::write_line("Test 10: Throw exception by adding node (fox) already in the list:");
    try {
      sentence.add_before(*sentence.find("fox"), node);
    } catch (const invalid_operation_exception& ex) {
      console::write_line("Exception message: {}", ex.message());
    }
    console::write_line();
    
    // Remove the 'fox' node, and then add it before the 'dog' node.
    // Indicate the node referred to by current.
    node = *sentence.find("fox");
    sentence.remove(node);
    sentence.add_before(*sentence.find("dog"), node);
    node = *sentence.find("dog");
    indicate_node(node, "Test 11: Move a referenced node (fox) before the current node (dog):");
    
    // Remove the node referred to by node.
    sentence.remove(node);
    node = sentence.find("dog") ? *sentence.find("dog") : linked_list_node<string>("dog");
    indicate_node(node, "Test 12: Remove current node (dog) and attempt to indicate it:");
    
    // Add the node after the 'brown' node.
    sentence.add_after(*sentence.find("brown"), node);
    indicate_node(node, "Test 13: Add node removed in test 12 after a referenced node (brown):");
    
    // The Remove method finds and removes the first node that that has the specified value.
    sentence.remove("old");
    display(sentence, "Test 14: Remove node that has the value 'old':");
    
    // When the linked list is cast to icollection(Of string), the add method adds a node to the end of the list.
    sentence.remove_last();
    auto& icoll = as<icollection<string>>(sentence);
    icoll.add("rhinoceros");
    display(sentence, "Test 15: Remove last node, cast to icollection, and add 'rhinoceros':");
    
    console::write_line("Test 16: Copy the list to an array:");
    // Create an array with the same number of elements as the linked list.
    auto sarray = array<string>(sentence.count());
    sentence.copy_to(sarray, 0);
    
    for (auto s : sarray)
      console::write_line(s);
    
    console::write_line();
    console::write_line("Test 17: linked list Contains 'jumps' = {0}", sentence.contains("jumps"));
    
    // Release all the nodes.
    sentence.clear();
    
    console::write_line();
    console::write_line("Test 18: Cleared linked list Contains 'jumps' = {0}", sentence.contains("jumps"));
  }
  
  static void display(const linked_list<string>& words, const string& test) {
    console::write_line(test);
    for (auto word : words)
      console::write(word + " ");
    console::write_line();
    console::write_line();
  }
  
  static void indicate_node(const linked_list_node<string>& node, const string& test) {
    console::write_line(test);
    auto l = node.list();
    if (!l) {
      console::write_line("Node '{0}' is not in the list.\n", node.value());
      return;
    }
    
    auto result = string_builder {"(" + node.value() + ")"};
    
    auto node_previous = node.previous();
    while (node_previous) {
      result.insert(0, node_previous->value() + " ");
      node_previous = node_previous->previous();
    }
    
    auto node_next = node.next();
    while (node_next) {
      result.append(" " + node_next->value());
      node_next = node_next->next();
    }
    
    console::write_line(result);
    console::write_line();
  }
};
 
startup_(example::main);
 
// This code produces the following output :
//
// The linked list values:
// the fox jumps over the dog
//
// Test 1: Add 'today' to beginning of the list:
// today the fox jumps over the dog
//
// Test 2: Move first node to be last node:
// the fox jumps over the dog today
//
// Test 3: Change the last node to 'yesterday':
// the fox jumps over the dog yesterday
//
// Test 4: Move last node to be first node:
// yesterday the fox jumps over the dog
//
// Test 5: Indicate last occurence of 'the':
// the fox jumps over (the) dog
//
// Test 6: Add 'lazy' and 'old' after 'the':
// the fox jumps over (the) lazy old dog
//
// Test 7: Indicate the 'fox' node:
// the (fox) jumps over the lazy old dog
//
// Test 8: Add 'quick' and 'brown' before 'fox':
// the quick brown (fox) jumps over the lazy old dog
//
// Test 9: Indicate the 'dog' node:
// the quick brown fox jumps over the lazy old (dog)
//
// Test 10: Throw exception by adding node (fox) already in the list:
// Exception message: The linked_list node belongs a linked_list.
//
// Test 11: Move a referenced node (fox) before the current node (dog):
// the quick brown jumps over the lazy old fox (dog)
//
// Test 12: Remove current node (dog) and attempt to indicate it:
// Node 'dog' is not in the list.
//
// Test 13: Add node removed in test 12 after a referenced node (brown):
// the quick brown (dog) jumps over the lazy old fox
//
// Test 14: Remove node that has the value 'old':
// the quick brown dog jumps over the lazy fox
//
// Test 15: Remove last node, cast to icollection, and add 'rhinoceros':
// the quick brown dog jumps over the lazy rhinoceros
//
// Test 16: Copy the list to an array:
// the
// quick
// brown
// dog
// jumps
// over
// the
// lazy
// rhinoceros
//
// Test 17: linked list Contains 'jumps' = true
//
// Test 18: Cleared linked list Contains 'jumps' = false
 

Remarks

xtd::collections::generic::linked_list <type_t> is a general-purpose linked list. It supports enumerators and implements the xtd::collections::generic::icollection interface, consistent with other collection classes in the xtd Framework.

xtd::collections::generic::linked_list <type_t> provides separate nodes of type xtd::collections::generic::linked_list_node <type_t>, so insertion and removal are O(1) operations.

You can remove nodes and reinsert them, either in the same list or in another list, which results in no additional objects allocated on the heap. Because the list also maintains an internal count, getting the xtd::collections::generic::linked_list::count property is an O(1) operation.

Each node in a xtd::collections::generic::linked_list <type_t> object is of the type xtd::collections::generic::linked_list_node <type_t>. Because the xtd::collections::generic::linked_list <type_t> is doubly linked, each node points forward to the xtd::collections::generic::linked_list_node::next node and backward to the xtd::collections::generic::linked_list_node::previous node.

If the xtd::collections::generic::linked_list <type_t> is empty, the xtd::collections::generic::linked_list::first and xtd::collections::generic::linked_list::last properties contain xtd::nullopt.

The xtd::collections::generic::linked_list <typ_t> class does not support chaining, splitting, cycles, or other features that can leave the list in an inconsistent state. The list remains consistent on a single thread. The only multithreaded scenario supported by xtd::collections::generic::linked_list <type_t> is multithreaded read operations.

Linq extension

• As xtd::collections::generic::linked_list <type_t> inherits the xtd::collections::generic::ienumerable <type_t> interface, it automatically inherits the xtd::collections::generic::extensions::enumerable <type_t> interface and at the same time all the methods of xtd::linq::enumerable.
• Thanks to xtd::linq, xtd::collections::generic::linked_list <type_t> can be manipulated by the classes of xtd::ranges::views and can be combined with std::ranges.
  The following example shows the xtd::ranges::views and std::ranges usage :

  #include <xtd/xtd>
   
  using namespace std::ranges::views;
   
  auto main() -> int {
    //string names[] = {"Burke", "Connor", "Frank", "Everett", "Albert", "George", "Harris", "David"};
    //auto names = std::initializer_list {"Burke"_s, "Connor"_s, "Frank"_s, "Everett"_s, "Albert"_s, "George"_s, "Harris"_s, "David"_s};
    //auto names = std::array<string, 8> {"Burke", "Connor", "Frank", "Everett", "Albert", "George", "Harris", "David"};
    //auto names = std::vector {"Burke"_s, "Connor"_s, "Frank"_s, "Everett"_s, "Albert"_s, "George"_s, "Harris"_s, "David"_s};
    //auto names = std::list {"Burke"_s, "Connor"_s, "Frank"_s, "Everett"_s, "Albert"_s, "George"_s, "Harris"_s, "David"_s};
    //auto names = std::unordered_set {"Burke"_s, "Connor"_s, "Frank"_s, "Everett"_s, "Albert"_s, "George"_s, "Harris"_s, "David"_s};
    //auto names = fixed_array<string, 8> {"Burke", "Connor", "Frank", "Everett", "Albert", "George", "Harris", "David"};
    //auto names = array {"Burke"_s, "Connor"_s, "Frank"_s, "Everett"_s, "Albert"_s, "George"_s, "Harris"_s, "David"_s};
    //auto names = list {"Burke"_s, "Connor"_s, "Frank"_s, "Everett"_s, "Albert"_s, "George"_s, "Harris"_s, "David"_s};
    //auto names = linked_list {"Burke"_s, "Connor"_s, "Frank"_s, "Everett"_s, "Albert"_s, "George"_s, "Harris"_s, "David"_s};
    //auto names = hash_set {"Burke"_s, "Connor"_s, "Frank"_s, "Everett"_s, "Albert"_s, "George"_s, "Harris"_s, "David"_s};
    //auto names = queue {"Burke"_s, "Connor"_s, "Frank"_s, "Everett"_s, "Albert"_s, "George"_s, "Harris"_s, "David"_s};
    //auto names = stack {"Burke"_s, "Connor"_s, "Frank"_s, "Everett"_s, "Albert"_s, "George"_s, "Harris"_s, "David"_s};
    auto names = {"Burke"_s, "Connor"_s, "Frank"_s, "Everett"_s, "Albert"_s, "George"_s, "Harris"_s, "David"_s};
   
    // xtd::linq query
    auto query1 = from(names)
      .where(_*method(&string::length) == 5)
      .order_by(_)
      .select(_*method(&string::to_upper));
    println(query1);
    
    // xtd::ranges query
    auto query2 = names
      | where(_*method(&string::length) == 5)
      | order_by(_)
      | select(_*method(&string::to_upper));
    println(query2);
    
    // std::ranges combined with xtd::ranges query
    auto query3 = names
      | filter(_*method(&string::length) == 5)
      | order_by(_)
      | transform(_*method(&string::to_upper));
    println(query3);
  }
   
  // This code produces the following output :
  //
  // [BURKE, DAVID, FRANK]
  // [BURKE, DAVID, FRANK]
  // [BURKE, DAVID, FRANK]

Performance considerations

As xtd::collections::generic::linked_list <type_t> instantiates and uses only the methods of std::list, the performance of xtd::collections::generic::linked_list <type_t> is practically identical to that of std::list.

Public Aliases
using	value_type
	Represents the list value type.
using	base_type
	Represents the list base type.
using	size_type
	Represents the list size type (usually xtd::usize).
using	reference
	Represents the reference of list value type.
using	const_reference
	Represents the const reference of list value type.

Public Constructors
	linked_list ()=default
	Initializes a new instance of the xtd::collections::generic::linked_list <type_t> class that is empty.
	linked_list (linked_list &&list)=default
	Move constructor with specified list.
	linked_list (const linked_list &list)
	Default copy constructor with specified list.
	linked_list (base_type &&list)
	Move constructor with specified base type list.
	linked_list (const base_type &list)
	Copy constructor with specified base type list.
	linked_list (const xtd::collections::generic::ienumerable< type_t > &collection)
	Initializes a new instance of the xtd::collections::generic::linked_list <type_t> class that contains elements copied from the specified xtd::collections::generic::ienumerable and has sufficient capacity to accommodate the number of elements copied.
	linked_list (std::initializer_list< type_t > items)
	Constructs the container with the contents of the specified initializer list, and allocator.
template<std::input_iterator input_iterator_t>
	linked_list (input_iterator_t first, input_iterator_t last)
	Constructs the container with the contents of the range [first, last).

Public Properties
auto	count () const noexcept -> size_type override
	Gets the number of nodes actually contained in the xtd::collections::generic::linked_list <type_t>.
auto	first () const noexcept -> xtd::optional< linked_list_node< type_t > >
	Gets the first node of the xtd::collections::generic::linked_list <type_t>.
auto	first () noexcept -> xtd::optional< linked_list_node< type_t > >
	Gets the first node of the xtd::collections::generic::linked_list <type_t>.
auto	items () const noexcept -> const base_type &
	Returns the underlying base type items.
auto	items () noexcept -> base_type &
	Returns the underlying base type items.
auto	last () const noexcept -> xtd::optional< linked_list_node< type_t > >
	Gets the last node of the xtd::collections::generic::linked_list <type_t>.
auto	last () noexcept -> xtd::optional< linked_list_node< type_t > >
	Gets the last node of the xtd::collections::generic::linked_list <type_t>.

Public Methods
auto	add_after (const linked_list_node< type_t > &node, const type_t &value) -> linked_list_node< type_t >
	Adds a new node containing the specified value after the specified existing node in the xtd::collections::generic::linked_list <type_t>.
auto	add_after (const linked_list_node< type_t > &node, linked_list_node< type_t > &new_node) -> void
	Adds the specified new node after the specified existing node in the xtd::collections::generic::linked_list <type_t>.
auto	add_before (const linked_list_node< type_t > &node, const type_t &value) -> linked_list_node< type_t >
	Adds a new node containing the specified value before the specified existing node in the xtd::collections::generic::linked_list <type_t>.
auto	add_before (const linked_list_node< type_t > &node, linked_list_node< type_t > &new_node) -> void
	Adds the specified new node before the specified existing node in the xtd::collections::generic::linked_list <type_t>.
auto	add_first (const type_t &value) -> linked_list_node< type_t >
	Adds a new node containing the specified value at the start of the xtd::collections::generic::linked_list <type_t>.
auto	add_first (linked_list_node< type_t > &node) -> void
	Adds the specified new node at the start of the xtd::collections::generic::linked_list <type_t>.
auto	add_last (const type_t &value) -> linked_list_node< type_t >
	Adds a new node containing the specified value at the end of the xtd::collections::generic::linked_list <type_t>.
auto	add_last (linked_list_node< type_t > &node) -> void
	Adds the specified new node at the end of the xtd::collections::generic::linked_list <type_t>.
auto	clear () -> void override
	Removes all elements from the xtd::collections::generic::linked_list <type_t>.
auto	contains (const type_t &value) const noexcept -> bool override
	Determines whether an element is in the xtd::colllections::generic::linked_list <type_t>.
auto	copy_to (xtd::array< type_t > &array, size_type array_index) const -> void override
	Copies the entire xtd::colllections::generic::linked_list <type_t> to a compatible one-dimensional array, starting at the specified index of the target array.
auto	find (const type_t value) const noexcept -> xtd::optional< linked_list_node< type_t > >
	Finds the first node that contains the specified value.
auto	find_last (const type_t value) const noexcept -> xtd::optional< linked_list_node< type_t > >
	Finds the last node that contains the specified value.
enumerator< value_type >	get_enumerator () const noexcept override
	Returns an enumerator that iterates through the xtd::collections::generic::linked_list <type_t>.
auto	remove (const type_t &item) noexcept -> bool override
	Removes the first occurrence of a specific object from the xtd::collections::generic::linked_list <type_t>.
auto	remove (linked_list_node< type_t > &node) -> void
	Removes the specified node from the xtd::collections::generic::linked_list <type_t>.
auto	remove_first () -> void
	Removes the node at the start of the xtd::collections::generic::linked_list <type_t>.
auto	remove_last () -> void
	Removes the node at the end of the xtd::collections::generic::linked_list <type_t>.
auto	to_string () const noexcept -> xtd::string override
	Returns a xtd::string that represents the current object.

Public Operators
auto	operator= (const linked_list &other) -> linked_list &=default
	Copy assignment operator. Replaces the contents with a copy of the contents of other.
auto	operator= (linked_list &&other) noexcept -> linked_list &
	Move assignment operator. Replaces the contents with those of other using move semantics (i.e. the data in other is moved from other into this container). other is in a valid but unspecified state afterwards.
auto	operator= (const std::initializer_list< type_t > &items) -> linked_list &
	Replaces the contents with those identified by initializer list ilist.
	operator const base_type & () const noexcept
	Returns a reference to the underlying base type.
	operator base_type & () noexcept
	Returns a reference to the underlying base type.

Additional Inherited Members
using	value_type
	Represents the xtd::collections::generic::icollection value type.
using	value_type
	Represents the xtd::collections::generic::ienumerable value type.
using	iterator
	Represents the iterator of xtd::collections::generic::ienumerable value type.
using	const_iterator
	Represents the const iterator of xtd::collections::generic::ienumerable value type.
using	iterator
	Represents the iterator of enumerable value type.
using	const_iterator
	Represents the const iterator of enumerable value type.
using	enumerable_type
	Represents the ienumerable enumerable type.
using	source_type
	Represents the ienumerable source type.
using	ienumerable
	Represents the ienumerable value type.
using	list
	Represents the list value type.
	object ()=default
	Create a new instance of the ultimate base class object.
virtual auto	equals (const object &obj) const noexcept -> bool
	Determines whether the specified object is equal to the current object.
virtual auto	get_hash_code () const noexcept -> xtd::usize
	Serves as a hash function for a particular type.
virtual auto	get_type () const noexcept -> type_object
	Gets the type of the current instance.
template<typename object_t>
auto	memberwise_clone () const -> xtd::unique_ptr_object< object_t >
	Creates a shallow copy of the current object.
virtual auto	begin () const -> const_iterator
	Returns an iterator to the first element of the enumerable.
virtual auto	cbegin () const -> const_iterator
	Returns an iterator to the first element of the enumerable.
virtual auto	cend () const -> const_iterator
	Returns an iterator to the element following the last element of the enumerable.
virtual auto	end () const -> const_iterator
	Returns an iterator to the element following the last element of the enumerable.
auto	aggregate (const std::function< type_t(const type_t &, const type_t &)> &funcfunc) const -> type_t
	Applies an accumulator function over a sequence.
auto	all (const std::function< bool(const type_t &)> &predicatepredicate) const -> bool
	Determines whether all elements of a sequence satisfy a condition.
auto	any () const noexcept -> bool
	Determines whether a sequence contains any elements.
auto	append (const type_t &element) const noexcept
	Appends a value to the end of the sequence.
auto	as_enumerable () const noexcept
	Returns the input typed as xtd::collections::generic::ienumerable <type_t>.
auto	average () const noexcept
	Computes the average of a sequence of source_t values.
auto	cast () const noexcept
	Casts the elements of an xtd::collections::generic::ienumerable to the specified type.
auto	chunk (xtd::usize size) const
	Splits the elements of a sequence into chunks of size at most size.
auto	concat (const ienumerable< type_t > &second) const noexcept
	Concatenates two sequences.
auto	contains (const type_t &value) const noexcept -> bool
	Determines whether a sequence contains a specified element by using the default equality comparer.
auto	count () const noexcept -> xtd::usize
	Returns the number of elements in current sequence.
auto	count_by (const std::function< key_t(const type_t &)> &key_selector) const noexcept
	Returns the count of elements in the current sequence grouped by key.
auto	default_if_empty () const noexcept
	Returns the elements of the specified sequence or the type parameter's default value in a singleton collection if the current sequence is empty.
auto	distinct () const noexcept
	Returns distinct elements from a sequence by using the default equality comparer to compare values.
auto	first_or_default (const std::function< bool(const type_t &)> &predicatepredicate, const type_t &default_value) const noexcept -> type_t
	Returns the first element of the sequence that satisfies a condition, or a specified default value if no such element is found.
auto	order () const
	Sorts the elements of a sequence in ascending order.
auto	order_by (const std::function< type_t(const type_t &)> &key_selector) const
	Sorts the elements of a sequence in ascending order according to a key.
auto	order_by_descending (const std::function< key_t(const type_t &)> &key_selector) const
	Sorts the elements of a sequence in descending order according to a key.
auto	select (auto &&selector) const
	Projects each element of a sequence into a new form.
auto	to_array () const noexcept -> xtd::array< type_t >
	Creates a xtd::array <type_t> from an xtd::collections::generic::ienumerable <type_t>.
auto	to_list () const noexcept -> xtd::collections::generic::list< type_t >
	Creates a xtd::collections::generic::list <type_t> from an xtd::collections::generic::ienumerable <type_t>.
auto	where (auto &&predicatepredicate) const
	Filters a sequence of values based on a predicate.
virtual auto	empty () const noexcept -> bool
	Checks whether the container is empty.
virtual auto	size () const noexcept -> xtd::usize
	Gets the number of elements contained in the xtd::collections::generic::icollection <type_t>.
virtual auto	operator<< (const type_t &item) -> icollection< type_t > &
	The shift left operator adds an item to the xtd::collections::generic::icollection <type_t>.
virtual auto	operator>> (const type_t &item) -> icollection< type_t > &
	The shift right operator removes the first occurrence of a specific object from the xtd::collections::generic::icollection <type_t>.
template<typename object_a_t, typename object_b_t>
static auto	equals (const object_a_t &object_a, const object_b_t &object_b) noexcept -> bool
	Determines whether the specified object instances are considered equal.
template<typename object_a_t, typename object_b_t>
static auto	reference_equals (const object_a_t &object_a, const object_b_t &object_b) noexcept -> bool
	Determines whether the specified object instances are the same instance.
static auto	to_const_iterator (typename source_collection_t::const_iterator &value, const source_collection_t &source_collection, const target_collection_t &target_collection) noexcept -> typename target_collection_t::const_iterator
	Converts source iterator to target iterator.
static auto	to_iterator (typename source_collection_t::const_iterator &value, const source_collection_t &source_collection, const target_collection_t &target_collection) noexcept -> typename target_collection_t::const_iterator
	Converts source iterator to target iterator.

Member Typedef Documentation

value_type

template<typename type_t, typename allocator_t>

using xtd::collections::generic::linked_list< type_t, allocator_t >::value_type

Represents the list value type.

base_type

template<typename type_t, typename allocator_t>

using xtd::collections::generic::linked_list< type_t, allocator_t >::base_type

Represents the list base type.

size_type

template<typename type_t, typename allocator_t>

using xtd::collections::generic::linked_list< type_t, allocator_t >::size_type

Represents the list size type (usually xtd::usize).

reference

template<typename type_t, typename allocator_t>

using xtd::collections::generic::linked_list< type_t, allocator_t >::reference

Represents the reference of list value type.

const_reference

template<typename type_t, typename allocator_t>

using xtd::collections::generic::linked_list< type_t, allocator_t >::const_reference

Represents the const reference of list value type.

Constructor & Destructor Documentation

linked_list() [1/8]

template<typename type_t, typename allocator_t>

xtd::collections::generic::linked_list< type_t, allocator_t >::linked_list ( )

default

Initializes a new instance of the xtd::collections::generic::linked_list <type_t> class that is empty.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

If the xtd::collections::generic::linked_list <type_t> is empty, the xtd::collections::generic::linked_list::first and xtd::collections::generic::linked_list::last properties contain std::nullopt.

This constructor is an O(1) operation.

linked_list() [2/8]

template<typename type_t, typename allocator_t>

xtd::collections::generic::linked_list< type_t, allocator_t >::linked_list ( linked_list< type_t, allocator_t > && list )

default

Move constructor with specified list.

Parameters

list	The xtd::collections::generic::linked_list <type_t> which elements will be moved from.

linked_list() [3/8]

template<typename type_t, typename allocator_t>

xtd::collections::generic::linked_list< type_t, allocator_t >::linked_list ( const linked_list< type_t, allocator_t > & list )

inline

Default copy constructor with specified list.

Parameters

linked_list

The xtd::collections::generic::linked_list <type_t> which elements will be inserted from.

linked_list() [4/8]

template<typename type_t, typename allocator_t>

xtd::collections::generic::linked_list< type_t, allocator_t >::linked_list ( base_type && list )

inline

Move constructor with specified base type list.

Parameters

list	The xtd::collections::generic::linked_list::base_type which elements will be moved from.

linked_list() [5/8]

template<typename type_t, typename allocator_t>

xtd::collections::generic::linked_list< type_t, allocator_t >::linked_list ( const base_type & list )

inline

Copy constructor with specified base type list.

Parameters

list	The xtd::collections::generic::linked_list::base_type which elements will be inserted from.

linked_list() [6/8]

template<typename type_t, typename allocator_t>

xtd::collections::generic::linked_list< type_t, allocator_t >::linked_list ( const xtd::collections::generic::ienumerable< type_t > & collection )

inline

Initializes a new instance of the xtd::collections::generic::linked_list <type_t> class that contains elements copied from the specified xtd::collections::generic::ienumerable and has sufficient capacity to accommodate the number of elements copied.

Parameters

collection

The xtd::collections::generic::ienumerable whose elements are copied to the new xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

If collection has no elements then the new xtd::collections::generic::linked_list <type_t> is empty, and the xtd::collections::generic::linked_list::first and xtd::collections::generic::linked_list::last properties contain xtd::nullopt.

This constructor is an O(n) operation, where n is the number of elements in collection.

linked_list() [7/8]

template<typename type_t, typename allocator_t>

xtd::collections::generic::linked_list< type_t, allocator_t >::linked_list ( std::initializer_list< type_t > items )

inline

Constructs the container with the contents of the specified initializer list, and allocator.

Parameters

items

The initializer list to initialize the elements of the container with.

linked_list() [8/8]

template<typename type_t, typename allocator_t>

template<std::input_iterator input_iterator_t>

xtd::collections::generic::linked_list< type_t, allocator_t >::linked_list ( input_iterator_t first, input_iterator_t last )

inline

Constructs the container with the contents of the range [first, last).

Parameters

first	The first iterator the range to copy the elements from.
last	The last iterator the range to copy the elements from.

Member Function Documentation

count()

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::count ( ) const -> size_type

inlinenodiscardoverridevirtualnoexcept

Gets the number of nodes actually contained in the xtd::collections::generic::linked_list <type_t>.

Returns

The number of nodes actually contained in the xtd::collections::generic::linked_list <type_t>.

Remarks

Retrieving the value of this property is an O(1) operation.

Implements xtd::collections::generic::icollection< type_t >.

first() [1/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::first ( ) const -> xtd::optional< linked_list_node< type_t > >

inlinenodiscardnoexcept

Gets the first node of the xtd::collections::generic::linked_list <type_t>.

Returns

The first xtd::collections::generic::linked_list_node <type_t> of the xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

If the xtd::collections::generic::linked_list <type_t> is empty, the xtd::collections::generic::linked_list::first and xtd::collections::generic::linked_list::last properties contain std::nullopt.

Retrieving the value of this property is an O(1) operation.

first() [2/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::first ( ) -> xtd::optional< linked_list_node< type_t > >

inlinenodiscardnoexcept

Gets the first node of the xtd::collections::generic::linked_list <type_t>.

Returns

The first xtd::collections::generic::linked_list_node <type_t> of the xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

If the xtd::collections::generic::linked_list <type_t> is empty, the xtd::collections::generic::linked_list::first and xtd::collections::generic::linked_list::last properties contain std::nullopt.

Retrieving the value of this property is an O(1) operation.

items() [1/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::items ( ) const -> const base_type &

inlinenodiscardnoexcept

Returns the underlying base type items.

Returns

The underlying base type items.

Remarks

Retrieving the value of this property is an O(1) operation.

items() [2/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::items ( ) -> base_type &

inlinenodiscardnoexcept

Returns the underlying base type items.

Returns

The underlying base type items.

Remarks

Retrieving the value of this property is an O(1) operation.

last() [1/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::last ( ) const -> xtd::optional< linked_list_node< type_t > >

inlinenodiscardnoexcept

Gets the last node of the xtd::collections::generic::linked_list <type_t>.

Returns

The last xtd::collections::generic::linked_list_node <type_t> of the xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

If the xtd::collections::generic::linked_list <type_t> is empty, the xtd::collections::generic::linked_list::first and xtd::collections::generic::linked_list::last properties contain std::nullopt.

Retrieving the value of this property is an O(1) operation.

last() [2/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::last ( ) -> xtd::optional< linked_list_node< type_t > >

inlinenodiscardnoexcept

Gets the last node of the xtd::collections::generic::linked_list <type_t>.

Returns

The last xtd::collections::generic::linked_list_node <type_t> of the xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

If the xtd::collections::generic::linked_list <type_t> is empty, the xtd::collections::generic::linked_list::first and xtd::collections::generic::linked_list::last properties contain std::nullopt.

Retrieving the value of this property is an O(1) operation.

add_after() [1/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::add_after ( const linked_list_node< type_t > & node, const type_t & value ) -> linked_list_node< type_t >

inline

Adds a new node containing the specified value after the specified existing node in the xtd::collections::generic::linked_list <type_t>.

Parameters

node	The xtd::collections::generic::linked_list_node <type_t> after which to insert value.
value	The value to add to the xtd::collections::generic::linked_list <type_t>.

Returns

The new xtd::collections::generic::linked_list_node <type_t> containing value.

Exceptions

xtd::invalid_operation_exception

`node` is not in the current xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

Retrieving the value of this property is an O(1) operation.

add_after() [2/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::add_after ( const linked_list_node< type_t > & node, linked_list_node< type_t > & new_node ) -> void

inline

Adds the specified new node after the specified existing node in the xtd::collections::generic::linked_list <type_t>.

Parameters

node	The xtd::collections::generic::linked_list_node <type_t> after which to insert new_node.
new_node	The new xtd::collections::generic::linked_list_node <type_t> to add to the xtd::collections::generic::linked_list <type_t>.

Exceptions

xtd::invalid_operation_exception

`node` is not in the current xtd::collections::generic::linked_list <type_t>. -or- `new_node` belongs to another xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

Retrieving the value of this property is an O(1) operation.

add_before() [1/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::add_before ( const linked_list_node< type_t > & node, const type_t & value ) -> linked_list_node< type_t >

inline

Adds a new node containing the specified value before the specified existing node in the xtd::collections::generic::linked_list <type_t>.

Parameters

node	The xtd::collections::generic::linked_list_node <type_t> before which to insert value.
value	The value to add to the xtd::collections::generic::linked_list <type_t>.

Returns

The new xtd::collections::generic::linked_list_node <type_t> containing value.

Exceptions

xtd::invalid_operation_exception

`node` is not in the current xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

Retrieving the value of this property is an O(1) operation.

add_before() [2/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::add_before ( const linked_list_node< type_t > & node, linked_list_node< type_t > & new_node ) -> void

inline

Adds the specified new node before the specified existing node in the xtd::collections::generic::linked_list <type_t>.

Parameters

node	The xtd::collections::generic::linked_list_node <type_t> before which to insert new_node.
new_node	The new xtd::collections::generic::linked_list_node <type_t> to add to the xtd::collections::generic::linked_list <type_t>.

Exceptions

xtd::invalid_operation_exception

`node` is not in the current xtd::collections::generic::linked_list <type_t>. -or- `new_node` belongs to another xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

Retrieving the value of this property is an O(1) operation.

add_first() [1/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::add_first ( const type_t & value ) -> linked_list_node< type_t >

inline

Adds a new node containing the specified value at the start of the xtd::collections::generic::linked_list <type_t>.

Parameters

value

The value to add at the start of the start of the xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

Retrieving the value of this property is an O(1) operation.

add_first() [2/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::add_first ( linked_list_node< type_t > & node ) -> void

inline

Adds the specified new node at the start of the xtd::collections::generic::linked_list <type_t>.

Parameters

node	The new xtd::collections::generic::linked_list_node <type_t> to add at the start of the xtd::collections::generic::linked_list <type_t>.

Exceptions

xtd::invalid_operation_exception

`node` is not in the current xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

Retrieving the value of this property is an O(1) operation.

add_last() [1/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::add_last ( const type_t & value ) -> linked_list_node< type_t >

inline

Adds a new node containing the specified value at the end of the xtd::collections::generic::linked_list <type_t>.

Parameters

value

The value to add at the start of the end of the xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

Retrieving the value of this property is an O(1) operation.

add_last() [2/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::add_last ( linked_list_node< type_t > & node ) -> void

inline

Adds the specified new node at the end of the xtd::collections::generic::linked_list <type_t>.

Parameters

node	The new xtd::collections::generic::linked_list_node <type_t> to add at the end of the xtd::collections::generic::linked_list <type_t>.

Exceptions

xtd::invalid_operation_exception

`node` is not in the current xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

Retrieving the value of this property is an O(1) operation.

clear()

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::clear ( ) -> void

inlineoverridevirtual

Removes all elements from the xtd::collections::generic::linked_list <type_t>.

Remarks

xtd::collections::generic::linked_list::count is set to 0, and references to other objects from elements of the collection are also released.

xtd::collections::generic::linked_list::capacity remains unchanged. To reset the capacity of the xtd::collections::generic::linked_list <type_t>, call the xtd::collections::generic::linked_list::trim_excess method or set the xtd::collections::generic::linked_list::capacity property directly. Decreasing the capacity reallocates memory and copies all the elements in the xtd::collections::generic::linked_list <type_t>. Trimming an empty xtd::collections::generic::linked_list <type_t> sets the capacity of the xtd::collections::generic::linked_list <type_t> to the default capacity.

This method is an O(n) operation, where n is xtd::collections::generic::linked_list::count.

Implements xtd::collections::generic::icollection< type_t >.

contains()

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::contains ( const type_t & value ) const -> bool

inlinenodiscardoverridevirtualnoexcept

Determines whether an element is in the xtd::colllections::generic::linked_list <type_t>.

Parameters

value

The object to locate in the xtd::colllections::generic::linked_list <type_t>. The value can be null for reference types.

Returns

true if item is found in the xtd::colllections::generic::linked_list <type_t>; otherwise, false.

Implements xtd::collections::generic::icollection< type_t >.

copy_to()

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::copy_to ( xtd::array< type_t > & array, size_type array_index ) const -> void

inlineoverridevirtual

Copies the entire xtd::colllections::generic::linked_list <type_t> to a compatible one-dimensional array, starting at the specified index of the target array.

Parameters

array	The one-dimensional Array that is the destination of the elements copied from xtd::colllections::generic::linked_list <type_t>. The Array must have zero-based indexing.
array_index	The zero-based index in array at which copying begins.

Exceptions

xtd::argument_out_of_range_exception

The number of elements in the source xtd::colllections::generic::linked_list <type_t> is greater than the available space from arrayIndex to the end of the destination array.

Remarks

This method uses xtd::array::copy to copy the elements.

The elements are copied to the xtd::array in the same order in which the enumerator iterates through the xtd::colllections::generic::linked_list <type_t>.

This method is an O(n) operation, where n is xtd::colllections::generic::linked_list::count.

Implements xtd::collections::generic::icollection< type_t >.

find()

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::find ( const type_t value ) const -> xtd::optional< linked_list_node< type_t > >

inlinenodiscardnoexcept

Finds the first node that contains the specified value.

Parameters

value

The value to locate in the xtd::collections::generic::linked_list <type_t>.

Returns

The first xtd::collections::generic::linked_list_node <type_t> that contains the specified value, if found; otherwise, xtd::nullopt.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

This method performs a linear search; therefore, this method is an O(n) operation, where n is xtd::collections::generic::linked_list::count.

find_last()

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::find_last ( const type_t value ) const -> xtd::optional< linked_list_node< type_t > >

inlinenodiscardnoexcept

Finds the last node that contains the specified value.

Parameters

value

The value to locate in the xtd::collections::generic::linked_list <type_t>.

Returns

The last xtd::collections::generic::linked_list_node <type_t> that contains the specified value, if found; otherwise, xtd::nullopt.

Remarks

xtd::collections::generic::linked_list <type_t> allows duplicate values.

This method performs a linear search; therefore, this method is an O(n) operation, where n is xtd::collections::generic::linked_list::count.

get_enumerator()

template<typename type_t, typename allocator_t>

enumerator< value_type > xtd::collections::generic::linked_list< type_t, allocator_t >::get_enumerator ( ) const

inlinenodiscardoverridevirtualnoexcept

Returns an enumerator that iterates through the xtd::collections::generic::linked_list <type_t>.

Returns

A xtd::collections::generic::.enumerator for the xtd::collections::generic::linked_list <type_t>.

Implements xtd::collections::generic::icollection< type_t >.

remove() [1/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::remove ( const type_t & item ) -> bool

inlineoverridevirtualnoexcept

Removes the first occurrence of a specific object from the xtd::collections::generic::linked_list <type_t>.

Parameters

item	The object to remove from the xtd::collections::generic::linked_list <type_t>.

Returns

true if item is successfully removed; otherwise, false. This method also returns false if item was not found in the xtd::collections::generic::linked_list <type_t>.

Remarks

If type typ_t implements the xtd::iequatable <type_t> generic interface, the equality comparer is the xtd::iequatable::equals method of that interface; otherwise, the default equality comparer is xtd::object::equals.

This method performs a linear search; therefore, this method is an O(n) operation, where n is xtd::collections::generic::linked_list::count.

Implements xtd::collections::generic::icollection< type_t >.

remove() [2/2]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::remove ( linked_list_node< type_t > & node ) -> void

inline

Removes the specified node from the xtd::collections::generic::linked_list <type_t>.

Parameters

node	The xtd::collections::generic::linked_list_node <type_t> to remove from the xtd::collections::generic::linked_list <type_t>.

Exceptions

xtd::invalid_operation_exception

node is not in the current xtd::collections::generic::linked_list <type_t>.

Remarks

This method is an O(1) operation.

remove_first()

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::remove_first ( ) -> void

inline

Removes the node at the start of the xtd::collections::generic::linked_list <type_t>.

Exceptions

xtd::invalid_operation_exception

The xtd::collections::generic::linked_list <type_t> is empty.

Remarks

This method is an O(1) operation.

remove_last()

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::remove_last ( ) -> void

inline

Removes the node at the end of the xtd::collections::generic::linked_list <type_t>.

Exceptions

xtd::invalid_operation_exception

The xtd::collections::generic::linked_list <type_t> is empty.

Remarks

This method is an O(1) operation.

to_string()

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::to_string ( ) const -> xtd::string

inlinenodiscardoverridevirtualnoexcept

Returns a xtd::string that represents the current object.

Returns

A string that represents the current object.

Reimplemented from xtd::object.

operator=() [1/3]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::operator= ( const linked_list< type_t, allocator_t > & other ) -> linked_list &=default

default

Copy assignment operator. Replaces the contents with a copy of the contents of other.

Parameters

other

Another container to use as data source.

Returns

This current instance.

operator=() [2/3]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::operator= ( linked_list< type_t, allocator_t > && other ) -> linked_list &

inlinenoexcept

Move assignment operator. Replaces the contents with those of other using move semantics (i.e. the data in other is moved from other into this container). other is in a valid but unspecified state afterwards.

Parameters

other

Another base type container to use as data source.

Returns

This current instance.

operator=() [3/3]

template<typename type_t, typename allocator_t>

auto xtd::collections::generic::linked_list< type_t, allocator_t >::operator= ( const std::initializer_list< type_t > & items ) -> linked_list &

inline

Replaces the contents with those identified by initializer list ilist.

Parameters

items

Initializer list to use as data source

Returns

This current instance.

operator const base_type &()

template<typename type_t, typename allocator_t>

xtd::collections::generic::linked_list< type_t, allocator_t >::operator const base_type & ( ) const

inlinenoexcept

Returns a reference to the underlying base type.

Returns

Reference to the underlying base type.

operator base_type &()

template<typename type_t, typename allocator_t>

xtd::collections::generic::linked_list< type_t, allocator_t >::operator base_type & ( )

inlinenoexcept

Returns a reference to the underlying base type.

Returns

Reference to the underlying base type.

---

The documentation for this class was generated from the following file:

• xtd.core/include/xtd/collections/generic/linked_list.hpp