Difference between linked lists and array of structs?

Question

what's the difference between those pieces of code?

1)

struct MyStruct
{
    int num;
} ms[2];

ms[0].num = 5;
ms[1].num = 15;

2)

struct MyStruct
{
    int num;
    MyStruct *next;
};

MyStruct *ms = new MyStruct;
ms->num = 5;
ms->next = new MyStruct;
ms->next->num = 15;

I'm probably a little confused about linked-lists and lists in general, are they useful to something in particular? Please explain me more.

Answer 1

Your first definition...

struct MyStruct
{
    int num;
} ms[1];

...creates a statically allocated array with a single element. You cannot change the size of the array while your program is running; this array will never hold more than one element. You can access items in the array by direct indexing; e.g., ms[5] would get you the sixth element in the array (remember, C and C++ arrays are 0-indexed, so the first element is ms[0]), assuming that you had defined an array of the appropriate size.

Your second definition...

struct MyStruct
{
    int num;
    MyStruct *next;
};

...creates a dynamically allocated linked list. Memory for this list is allocated dynamically during runtime, and the linked list can grow (or shrink) during the lifetime of the program. Unlike arrays, you cannot directly access any element in the list; to get to the sixth element you have to start at the first element and then iterate 5 times.

Answer 2

Regarding errors you have in your code, the first one constructs a static number of MyStruct elements and store them in ms array, so ms is an array of MyStruct structures, of course in this you meant it to be of 2 elements only, later on you can't add any other element to ms array and though you have limited the number of MyStruct elements, while in the second case when you have a linked list you can chain as many MyStruct elements as you want and this will lead to dynamic number of MyStruct elements, the second case let you add as many MyStruct as you want during the run time, the second case should look like this conceptually in memory:

[ MyStruct#1 ] ----> [ MyStruct#2 ] ----> [ NULL ]

NULL though could be a MyStruct#3 for example, while the first one:

[ MyStruct#1 ] ----> [ MyStruct#2 ]

and that's it, no MyStruct#3 can be added.

Now let's go through the code you wrote:

struct MyStruct
{
    int num;
} ms[1];

ms[1] really means create me an ms array of one MyStruct element.
The code next assume you created two:

ms[0].num = 5;
ms[1].num = 15

Hence it should have been:

struct MyStruct
{
    int num;
} ms[2];

And it will work fine! and keep in mind the simple illustration I made for it:
[ MyStruct#1 ] ----> [ MyStruct#2 ]

Second Case:

struct MyStruct
{
    int num;
    MyStruct *next;
};

MyStruct *ms = new MyStruct;
ms->num = 5;
ms->next = new MyStruct;
ms->next->num = 15;

This code uses the C++ operator new if you save your source code as .cpp you'll be able to compile as C++ application with no errors, while for C, the syntax should change like so:

struct MyStruct
{
    int num;
    MyStruct *next;
};

MyStruct *ms = (MyStruct *) malloc(sizeof MyStruct);
ms->num = 5;
ms->next = (MyStruct *) malloc(sizeof MyStruct);
ms->next->num = 15;

and don't forget to include #include <stdlib.h> for the malloc() function, you can read more about this function here.
And as the first case recall my illustration for the linked-list:
[ MyStruct#1 ] ----> [ MyStruct#2 ] ----> [ NULL ]

Where NULL is actually the next element of the ms->next MyStruct structure, to explain it more recall that ms->next is a pointer of MyStruct and we have allocated it a space in the heap so now it's pointing to a block of memory of the same size of MyStruct structure. Finally here is a Stackoverflow question about when to use a linked-list and when to use an array so you can get exactly why people all around the world prefer linked-list sometimes and array other times.

Answer 3

Oh, my friend, there are dozens of different kinds of data structures that pretty much just hold a bunch of num values or whatever. The reason programmers don't just use arrays for everything is the differences in the amount of memory required, and the ease of doing whichever operations are most important for your particular needs.

Linked lists happen to be very quick at adding or removing individual items. The trade off is that finding an item in the middle of the list is relatively slow, and the extra memory required by the next pointers. A properly-sized array is very compact in memory, and you can access an item in the middle very quickly, but to add a new item at the end you either have to know the maximum number of elements beforehand, which is often impossible or wastes memory, or reallocate a larger array and copy everything over, which is slow.

Therefore, someone who doesn't know how big their list needs to be, and who mostly only needs to deal with items at the beginning or end of the list or always loops over the entire list, and cares more about execution speed than saving a few bytes of memory, is very likely to choose a linked list over an array.

Answer 4

The main differences between lists and arrays in general:

• Ordering in lists is explicit; each element stores the location of the preceding/succeeding element. Ordering in arrays is implicit; each element is assumed to have a preceding/succeeding element. Note that a single list may contain multiple orderings. For example, you could have something like

  struct dualList {
  T data1;
  K data2;
  struct dualList *nextT;
  struct dualList *nextK;
  };

  that allows you to order the same list two different ways, one by data1 and the other by data2.

• Adjacent array elements are in adjacent memory locations; adjacent list elements don't have to be in adjacent locations.

• Arrays offer random access to their elements; lists only offer sequential access (i.e., you have to walk down the list to find an element).

• Arrays are (usually) fixed in length¹ - adding elements to or removing elements from the array doesn't change the array's size. Lists can grow or shrink as needed.

Lists are great for maintaining a dynamically changing sequence of values, especially if the values need to remain ordered. They're not so hot for storing relatively static data that needs to be retrieved quickly and frequently, since you can't access elements randomly.

---

1. You can get around this by declaring memory dynamically, and then use realloc to resize that memory block as needed, but it needs to be done carefully and can be a bit of a PITA.

Answer 5

Linked lists are useful when element ordering is important, and the number of elements is not known in advance. Besides, accessing an element in linked list takes O(n) time. When you look for an element in a list, in the worst case, you'll have to look at every element of a list.

For array, the number must be known in advance. When you define an array in C, you have to pass it its size. On the other hand, accessing an array element takes O(1) time, since an element can be addressed by index. With linked list, that is not possible.

However, that is not C++ related question, since the concept of linked list and array is not tied to C++.

Answer 6

An array is a contiguous pre-allocated block of memory whereas a linked list is a collection of runtime allocated ( malloc ) pieces of memory ( not necessarily contiguous ) linked to each other via pointers ( *next ). You would generally use an array of structs if you know at compile time the maximum number of elements you need to store. A linked list of structs however is useful if you don't know the maximum number of elements that will need to be stored. Also with a linked list the number of elements may change, add and remove elements.