What Are Data Structures? Linked Lists

Updated on May 15, 2018

What is a data structure?

A data structure is a method for organising a set of data. The structure is defined by how the data is stored and how operations, such as data access, insertion and deletion, are performed on the stored data. Data structures are essential tools for programmers, as each structure has a set of benefits that make it useful for solving certain types of problem.

Linked Lists

General idea

A linked list consists of a series of nodes. Each node stores a piece of data and a pointer that points to the next node in the list. There are two special pointers within the list:

  1. The head pointer, this points to the first node in the list. The head pointer is all that is needed to access the whole list.
  2. A null pointer, this indicates that the end of the list has been reached (If the head is a null pointer then this represents an empty list).

Because pointers are used to link the data together, there is no requirement for the list's data to be stored contiguously in memory.

An example linked list of characters, used to store the word 'test'. Data stored within a node is coloured blue.
An example linked list of characters, used to store the word 'test'. Data stored within a node is coloured blue.

Implementation

template <class T>
class LinkedList{
	public:
		LinkedList() : head{nullptr} {}
		~LinkedList(){
			while(head != nullptr){
				Node* previous{head};
				head = head->next;
				delete previous;	
			}
		}
		void Insert(const T data_in);
		T At(const int position) const;
		void Delete(const int position);
	private:
		struct Node{
			T data;
			Node* next;
		};
		Node* head;
};

The above code declares a template linked list class in C++. The only data that the class directly stores is a head pointer. The structure of the list node's also needs to be declared (but this could be moved out of the class). The class contains member functions to insert a new piece of data and access or delete the data at a certain position within the list.

The constructor just initialises the head pointer as a null pointer, i.e. a new list starts out as an empty list. The destructor is much more important. It traverses over the whole list and frees up the memory used to store each of the list's nodes. This is crucial as new list nodes will be created using dynamically allocated memory and hence they need deallocating when the list is destroyed.

Insertion

template <class T>
void LinkedList<T>::Insert(const T data_in){
	Node* new_node{ new Node };
	new_node->data = data_in;
	new_node->next = head;
	head = new_node;
}

The above code implements the insertion method for our linked list class. Firstly, it allocates memory to create a new node. It then sets the node's data to the user input data and sets the node to point to the current list. The list head is then changed to point to the new node.

An example insertion of the character 't' into a linked list currently storing the word 'est'. New pointers are coloured red.
An example insertion of the character 't' into a linked list currently storing the word 'est'. New pointers are coloured red.

This method of insertion inserts every element from the head position. Making this choice leads to insertions being very simple, only involving the assignment of pointers. This leads to the insertion operation scaling as O(1) i.e. insertion is very fast.

Accessing data

template <class T>
T LinkedList<T>::At(const int position) const{
	int current_position{0};
	Node* current{head};
	while (current != nullptr && current_position < position) {
		current = current->next;
		current_position++;
	}
	if (current == nullptr) {
		/*deal with the element not being found
		because the position is out of range*/
	}
	return current->data;
}

The above code implements the method for accessing data within our linked list class. It creates a local pointer to store the current node and an integer representing the current node's position within the list. The current pointer is initialised to the list head (which we choose to label as the 0th position). It is then repeatedly moved onto the next node. This loops until either the user's requested position or the end of the list has been reached. If the current pointer ends up as a null pointer then the user has requested a position that is out of the list's range and the programmer needs to choose how to deal with this. Otherwise, we simply return the data pointed to by the current pointer.

Accessing the first few lists elements will be fast, roughly O(1). However, the general access time scales as O(n), where n is the size of the list. This is because the list has to be traversed sequentially (in order from the start of the list). This will make accessing the data in long lists very slow.

Deletion

template <class T>
void LinkedList<T>::Delete(const int position){
	int current_position{0};
	Node* current{head};
	Node* previous{nullptr};
	while (current != nullptr && current_position < position) {
		previous = current;
		current = current->next;
		current_position++;
	}
	if (current == nullptr) {
		/*deal with the element position
		being out of range*/
	}
	if (position == 0) {
		head = head->next;
	} else {
		previous->next = current->next;
	}
	delete current;
}

The above code implements the deletion method for our linked list class. It is very similar to the previously implemented access method. It traverses the list in exactly the same way but also stores a pointer to the previously visited node. The previous node is then changed to point to the node after the current node (basically cutting the current node out of the list). When the head is deleted, there is no previous node so the head pointer is modified instead. The current node is then deleted from memory.

An example of deleting the character 'e' from a linked list currently storing the word 'test'. The deleted node is crossed out along with its associated pointers. Note how the new pointer is assigned to reconnect the list nodes.
An example of deleting the character 'e' from a linked list currently storing the word 'test'. The deleted node is crossed out along with its associated pointers. Note how the new pointer is assigned to reconnect the list nodes.

The time efficiency of deletion is identical to accessing list elements. The first few elements are O(1) but generally it is O(n).

Advantages and disadvantages

+ The linked list is a dynamic structure. It allows resizing at runtime and doesn't need an to be initialised as a specific size during compile time.

+ Insertion can be implemented quickly, independent of the data size.

+ Deletion could also be implemented quickly if elements were removed from the head.

- The list wastes some memory by storing a pointer alongside each piece of data.

- Elements must be accessed sequentially, much slower than random access.

- Reverse traversal (from back to front) of a linked list is very difficult.

Uses

Like all other data structures, a linked list should be used when it's attributes are suitable for the problem. Some examples being:

  • To store a history of visited web pages. The most recently visited web page being added to the top of the list makes sense. Displaying the history will also naturally require the whole list to be accessed sequentially.
  • To store the enemies within a video game. Essential operations such as collision checking will need to be performed on the whole group of enemies. Potential deletions would also be performed as a result of the collision check. Therefore, the lack of fast random access for specific enemies is not a problem.
  • To implement other data structures. Linked lists can be used as the underlying implementation of other data structures, such as variable sized arrays, stacks and queues.
  • Linked lists are often used to resolve collisions in hash tables.

Doubly linked list

A doubly linked list contains nodes that also store a pointer to the previous node. This removes the difficulty of reverse traversal, at the cost of storing an extra pointer within each node. Doubly linked lists will also typically store a tail pointer, pointing to the last element in the list. A tail pointer enables the possibility of fast insertion or deletion of elements from the tail.

Circularly linked list

Circularly linked lists are created by having a node that points back to a previous list node (creating a circular loop). This means that the list can be fully traversed by starting from any node, not just the head as in the case of a linear linked list. Circular linked lists are useful for applications where the list needs to cycled through repeatedly.

An example circularly linked list of coordinate points, used to store the vertices of a triangle.
An example circularly linked list of coordinate points, used to store the vertices of a triangle.

Test your knowledge

view quiz statistics

Alternative data structures

Questions & Answers

    © 2018 Sam Brind

    Comments

      0 of 8192 characters used
      Post Comment

      No comments yet.

      working

      This website uses cookies

      As a user in the EEA, your approval is needed on a few things. To provide a better website experience, owlcation.com uses cookies (and other similar technologies) and may collect, process, and share personal data. Please choose which areas of our service you consent to our doing so.

      For more information on managing or withdrawing consents and how we handle data, visit our Privacy Policy at: https://owlcation.com/privacy-policy#gdpr

      Show Details
      Necessary
      HubPages Device IDThis is used to identify particular browsers or devices when the access the service, and is used for security reasons.
      LoginThis is necessary to sign in to the HubPages Service.
      Google RecaptchaThis is used to prevent bots and spam. (Privacy Policy)
      AkismetThis is used to detect comment spam. (Privacy Policy)
      HubPages Google AnalyticsThis is used to provide data on traffic to our website, all personally identifyable data is anonymized. (Privacy Policy)
      HubPages Traffic PixelThis is used to collect data on traffic to articles and other pages on our site. Unless you are signed in to a HubPages account, all personally identifiable information is anonymized.
      Amazon Web ServicesThis is a cloud services platform that we used to host our service. (Privacy Policy)
      CloudflareThis is a cloud CDN service that we use to efficiently deliver files required for our service to operate such as javascript, cascading style sheets, images, and videos. (Privacy Policy)
      Google Hosted LibrariesJavascript software libraries such as jQuery are loaded at endpoints on the googleapis.com or gstatic.com domains, for performance and efficiency reasons. (Privacy Policy)
      Features
      Google Custom SearchThis is feature allows you to search the site. (Privacy Policy)
      Google MapsSome articles have Google Maps embedded in them. (Privacy Policy)
      Google ChartsThis is used to display charts and graphs on articles and the author center. (Privacy Policy)
      Google AdSense Host APIThis service allows you to sign up for or associate a Google AdSense account with HubPages, so that you can earn money from ads on your articles. No data is shared unless you engage with this feature. (Privacy Policy)
      Google YouTubeSome articles have YouTube videos embedded in them. (Privacy Policy)
      VimeoSome articles have Vimeo videos embedded in them. (Privacy Policy)
      PaypalThis is used for a registered author who enrolls in the HubPages Earnings program and requests to be paid via PayPal. No data is shared with Paypal unless you engage with this feature. (Privacy Policy)
      Facebook LoginYou can use this to streamline signing up for, or signing in to your Hubpages account. No data is shared with Facebook unless you engage with this feature. (Privacy Policy)
      MavenThis supports the Maven widget and search functionality. (Privacy Policy)
      Marketing
      Google AdSenseThis is an ad network. (Privacy Policy)
      Google DoubleClickGoogle provides ad serving technology and runs an ad network. (Privacy Policy)
      Index ExchangeThis is an ad network. (Privacy Policy)
      SovrnThis is an ad network. (Privacy Policy)
      Facebook AdsThis is an ad network. (Privacy Policy)
      Amazon Unified Ad MarketplaceThis is an ad network. (Privacy Policy)
      AppNexusThis is an ad network. (Privacy Policy)
      OpenxThis is an ad network. (Privacy Policy)
      Rubicon ProjectThis is an ad network. (Privacy Policy)
      TripleLiftThis is an ad network. (Privacy Policy)
      Say MediaWe partner with Say Media to deliver ad campaigns on our sites. (Privacy Policy)
      Remarketing PixelsWe may use remarketing pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to advertise the HubPages Service to people that have visited our sites.
      Conversion Tracking PixelsWe may use conversion tracking pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to identify when an advertisement has successfully resulted in the desired action, such as signing up for the HubPages Service or publishing an article on the HubPages Service.
      Statistics
      Author Google AnalyticsThis is used to provide traffic data and reports to the authors of articles on the HubPages Service. (Privacy Policy)
      ComscoreComScore is a media measurement and analytics company providing marketing data and analytics to enterprises, media and advertising agencies, and publishers. Non-consent will result in ComScore only processing obfuscated personal data. (Privacy Policy)
      Amazon Tracking PixelSome articles display amazon products as part of the Amazon Affiliate program, this pixel provides traffic statistics for those products (Privacy Policy)