stoimen's web log

Arrays vs. Linked List

If we talk about arrays and linked lists we know the pros and cons about both of them. No matter which programming language we use arrays benefit from direct access to its items, while linked lists are more memory efficient for particular tasks.

Array & Linked List

The items of a linked list keep a reference to their successor, so we can easily walk through the entire list. However we don’t have direct access to its elements. Thus we can’t go directly to its middle element! Even more – in particular implementations of a linked list we don’t know its length. But in some cases linked lists are far more effective than arrays. For instance reversing an array of non-numeric values require constant additional memory, but also requires n/2 exchanges. The same taks using linked lists is not only performed in linear time, but doesn’t require any additional memory. The only thing we need to do is to reverse the links – no movement of values and the items remain at the same place in the memory.

Merging of two arrays often require more space (proportional of the space of the two arrays) or many exchanges in case we try to do it in place. The same task on linked lists is far more effective with only changing pointers and without moving the values. Continue reading →

Introduction

The linked list is a data structure in which the items are ordered in a linear way. Although modern programming languages support very flexible and rich libraries that works with arrays, which use arrays to represent lists, the principles of building a linked list remain very important. The way linked lists are implemented is a ground level in order to build more complex data structures such as trees.

It’s true that almost every operation we can perform on a linked list can be done with an array. It’s also true that some operations can be faster on arrays compared to linked lists.

However understanding how to implement the basic operations of a linked list such as INSERT, DELETE, INSERT_AFTER, PRINT and so on is crucial in order to implement data structures as rooted trees, B-trees, red-black trees, etc.

Overview

Unlike arrays where we don’t have pointers to the next and the previous item, the linked list is designed to support such pointers. In some implementations there is only one pointer pointing to the successor of the item. This kind of data structures are called singly linked lists. In this case the the last element doesn’t have a successor, so the pointer to its next element usualy is NULL. However the most implemented version of a linked list supports two pointers. These are the so called doubly linked lists.

Arrays vs. linked list — Arrays items are defined by their indices, while the linked list item contains a pointer to its predecessor and his successor!

Continue reading →