China
Africa
Explore chapters and articles related to this topic
Simulation Techniques
Published in Harry G. Perros, An Introduction to IoT Analytics, 2021
A linked list provides a mechanism whereby each data element of a list of data elements is stored in a different part of the memory; i.e., they are not stored in contiguous memory locations as in an array. This permits data elements to be dynamically added or removed at runtime. In order to access the data elements in the list, we store along with a data element the address of the next data element. This pointer is referred to as a link. The data element and the link is referred to as a node. In general, a node may consist of a number of data elements and links. Linked lists are drawn graphically as shown in Figure 3.11. Each node is represented by a box consisting of as many compartments as the number of data elements and links stored in the node. In the example given in Figure 3.11, each node consists of three compartments. The first one has the clock value, the second the type of event, and the third the pointer to the next node. The pointer head points to the first node in the list. The pointer of the last node is set to NULL, a special value indicating that this is the last node in the linked list. Due to the fact that two successive nodes are connected by a single pointer, this data structure is known as a singly linked list.
Introduction to Algorithms and Data Structures
Published in Sriraman Sridharan, R. Balakrishnan, Foundations of Discrete Mathematics with Algorithms and Programming, 2019
Sriraman Sridharan, R. Balakrishnan
Disadvantages of linked list representation: We have no direct access to the ith node of the list. To access the ith node of the list, we have to move from the first node of the list in a step-by-step manner. The complexity of performing such an operation in the worst case is O(n) where n is the number of nodes currently in the list. Also, no manipulation of field names is possible since the field names are strings of characters.
Parallel Algorithms
Published in Vivek Kale, Parallel Computing Architectures and APIs, 2019
This section shows that a parallel approach can also be useful when working with pointer-based data structures, such as a linked list. A singly linked list L consists of a number of nodes where each node (except the last one) holds a pointer to the next node in the list (Figure 8.5a). Besides this pointer, a node also usually holds a value (that depends on the application) and other necessary information.
Evaluation of the effectiveness of neighbors’ selection algorithms in the random cellular automata model of unconstrained grain growth
Published in Materials and Manufacturing Processes, 2023
Mateusz Sitko, Michal Czarnecki, Kacper Pawlikowski, Lukasz Madej
For the second group, the following specific conclusions can be drawn: The use of different floating-point representations does not significantly impact the performance of the analyzed algorithms.In the case of step() stage, execution times are seemingly correlated with the number of conditional branches. In the prepare() stage, the memory bandwidth is the bottleneck that can only replace by the change in the hardware used for the calculations.A one-sided linked list is not beneficial for the optimal use of cache memory.
Algorithmic Improvements to MCNP5 for High-Resolution Fusion Neutronics Analyses
Published in Fusion Science and Technology, 2018
Scott W. Mosher, Stephen C. Wilson
In ORNL-TN, a doubly linked list data structure13 is used when editing the cell definitions. Unlike arrays, inserting and deleting elements in a linked list are O(1) operations because they merely involve the manipulation of the links between elements. At the beginning of the editing process, a temporary array is allocated to have the same size as the existing cell definitions array. This is easily accommodated because even for very large models, the array consumes only a few megabytes of memory. Then for each cell, the definition elements are copied from the definitions array into a linked list structure where the editing steps are performed. When editing is completed, the elements from the linked list are copied onto the end of the temporary array. When all cell definitions have been processed, the temporary array is copied onto the definition array, overwriting the original contents, and the temporary array is de-allocated. Using this algorithm, the complexity of the cell editing process is O(n) in the asymptotic limit.
Threadsafe Dynamic Neighbor Lists for Monte Carlo Ray Tracing
Published in Nuclear Science and Engineering, 2020
Sterling M. Harper, Paul K. Romano, Benoit Forget, Kord S. Smith
Linked lists come with some disadvantages over vectors. Linked lists require more memory because each element in the list must hold a pointer to the next element. The elements are also not contiguous in memory, which can hurt runtime performance because of poor spatial locality resulting in cache misses.