Linked List Memory

[Arnold Gilgen]

TheLinked List is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers. It is implemented on the heap memory rather than the stack memory. This article discusses the reason behind it.

On the other hand, a linked list has the major advantage of dynamically expanding itself when needed without worrying about memory consumption. This is the reason why heap is preferred for storing linked list-object.

The above code gives the verdict as SEGMENTATION FAULT. The reason behind it is that during the creation of the linked list in the stack memory, all the objects created by a function will be disappeared as the stack frame is popped whenever the function ends or returns. Refer to this article to know the reason behind the popping of stack frame whenever function ends.

In a linked list, when there is a need to store more data, we can allocate the memory at run-time by using malloc or a new function in C/ C++. So dynamic memory allocation reserve size from heap area, therefore, a linked list is stored in heap memory.

If there is a need to store linked lists in the stack area then implement linked lists without using malloc or a new function.

Let's imagine that we want to store the integer "17" in a variable myNumber. For simplicity, let's assume the integer is stored as two bytes (16 bits), and the address in memory to myNumber is 0x7F30.

0x7F30 is actually the address to the first of the two bytes of memory where the myNumber integer value is stored. When the computer goes to 0x7F30 to read an integer value, it knows that it must read both the first and the second byte, since integers are two bytes on this specific computer.

The example above shows how an integer value is stored on the simple, but popular, Arduino Uno microcontroller. This microcontroller has an 8 bit architecture with 16 bit address bus and uses two bytes for integers and two bytes for memory addresses. For comparison, personal computers and smart phones use 32 or 64 bits for integers and addresses, but the memory works basically in the same way.

The image below shows how an array of integers myArray = [3,5,13,2] is stored in memory. We use a simple kind of memory here with two bytes for each integer, like in the previous example, just to get the idea.

The computer has only got the address of the first byte of myArray, so to access the 3rd element with code myArray[2] the computer starts at 0x7F28 and jumps over the two first integers. The computer knows that an integer is stored in two bytes, so it jumps 2x2 bytes forward from 0x7F28 and reads value 13 starting at address 0x7F32.

When removing or inserting elements in an array, every element that comes after must be either shifted up to make place for the new element, or shifted down to take the removed element's place. Such shifting operations are time consuming and can cause problems in real-time systems for example.

Manipulating arrays is also something you must think about if you are programming in C, where you have to explicitly move other elements when inserting or removing an element. In C this does not happen in the background.

A big benefit with using linked lists is that nodes are stored wherever there is free space in memory, the nodes do not have to be stored contiguously right after each other like elements are stored in arrays. Another nice thing with linked lists is that when adding or removing nodes, the rest of the nodes in the list do not have to be shifted.

Each node takes up four bytes. Two bytes are used to store an integer value, and two bytes are used to store the address to the next node in the list. As mentioned before, how many bytes that are needed to store integers and addresses depend on the architecture of the computer. This example, like the previous array example, fits with a simple 8-bit microcontroller architecture.

Unlike with arrays, the nodes in a linked list are not placed right after each other in memory. This means that when inserting or removing a node, shifting of other nodes is not necessary, so that is a good thing.

Something not so good with linked lists is that we cannot access a node directly like we can with an array by just writing myArray[5] for example. To get to node number 5 in a linked list, we must start with the first node called "head", use that node's pointer to get to the next node, and do so while keeping track of the number of nodes we have visited until we reach node number 5.

The createNode() function allocates memory for a new node, fills in the data part of the node with an integer given as an argument to the function, and returns the pointer (memory address) to the new node.

Inside the main() function, four nodes are created, linked together, printed, and then the memory is freed. It is good practice to free memory after we are done using it to avoid memory leaks. Memory leak is when memory is not freed after use, gradually taking up more and more memory.

To print the linked list in the code above, the printList() function goes from one node to the next using the "next" pointers, and that is called "traversing" or "traversal" of the linked list. You will learn more about linked list traversal and other linked list operations on the Linked Lists Oprations page.

I need to store a large amount of information, say for example 'names' in a java List. The number of items can change (or in short I cannot predefine the size). I am of the opinion that from a memory allocation perspective LinkedList would be a better option than ArrayList, as for an ArrayList once the max size is reached, automatically the memory allocation doubles and hence there would always be a chance of more memory being allocated than what is needed.

I understand from other posts here that individual elements stored in a LinkedList takes more space than an ArrayList as LinkedList also needs to store the node information, but I am still guessing for the scenario I have defined LinkedList might be a better option. Also, I do not want to get into the performance aspect (fetching, deleting etc) , as much has already been discussed on it.

LinkedList might allocate fewer entries, but those entries are astronomically more expensive than they'd be for ArrayList -- enough that even the worst-case ArrayList is cheaper as far as memory is concerned.

See e.g. -measurer/blob/master/ElementCostInDataStructures.txt : LinkedList consumes 24 bytes per element, while ArrayList consumes in the best case 4 bytes per element, and in the worst case 6 bytes per element. (Results may vary depending on 32-bit versus 64-bit JVMs, and compressed object pointer options, but in those comparisons LinkedList costs at least 36 bytes/element, and ArrayList is at best 8 and at worst 12.)

To be clear, even in the worst case, ArrayList is 4x smaller than a LinkedList with the same elements. The only possible way to make LinkedList win is to deliberately fix the comparison by calling ensureCapacity with a deliberately inflated value, or to remove lots of values from the ArrayList after they've been added.

In short, it's basically impossible to make LinkedList win the memory comparison, and if you care about space, then calling trimToSize() on the ArrayList will instantly make ArrayList win again by a huge margin. Seriously. ArrayList wins.

Unless you have millions of entries, the size of the collection is unlikely to matter. What will matter first is the size of entries which is the same regardless of the collection used.

Once you have got past the initial capacity of the array list, the size of the backing will be between 1 and 2 references times the number of entries. This is due to strategy used to grow the backing array.

For a linked list, each node occupies AT LEAST 3 times the number of entries, because each node has a next and prev reference as well as the entry reference. (And in fact, it is more than 3 times, because of the space used by the nodes' object headers and padding. Depending on the JVM and pointer size, it can be as much as 6 times.)

Everyone who worked with C++ for longer than twelve seconds has noticed that keeping track of pointers is somehwat complicated. You have all kinds of wonderful new problems that you never knew you could have in other languages:

The list I want to implement is a doubly linked list, so each element has a pointer forward and one backwards pointer. I chose to use an std::shared_ptr for the forwards pointer, since this enables me to use std::weak_ptrs for iterators. Using std::shared_ptrs for backwards pointers as well would force the reference count for each pointer to be at least 1, so those are going to be std::weak_ptrs as well.

The interesting one remains what to do with the end iterator, since it needs to be mostly valid, and have a reference to the last element. Here I copied the STL and implemented added the value to my list entries as a pointer, which is is a null pointer for the end element. This pointer is a std::unique_ptr since no other construct never actually needs access to the raw pointer of the value.

Originally, I did not have an O(n log n) algorithm for sorting, because I was lazy and just implemented bubble sort. I thought it would be way harder to implement a fast sorting algorithm without random access in your data structure. I was wrong of course, since you can easily build merge sort, using pieces already included in the list:

Does between two and three times as many allocations as std::list. This mostly comes down to the extras guard blocks that need to be allocated for shared pointers (the guard block stores the use counts). Additionally, I need to do two allocations for empty lists while the STL does none.

3a8082e126