Linked List Data Structure
Linked List Data Structure
Embedded Files
A linked list is a type of list (most similar to an arraylist) that can expand and shrink dynamically as elements are added and deleted. When searching a linked list, we must start at the root node and use pointers to go to from node to node sequentially. The reason for this is that linked list cells are not stored contiguously in memory so they must have pointers to the next node and start at the root. Otherwise, we would not be able to locate nodes or their values.
This is the general architecture of a list:
Below is basic code for a Singly Linked List in C++:
using namespace std;
#include<iostream>
/*
Creating the node class. Each node will have a value of type int and a pointer to the next node in the list
*/
class Node {
public:
int value;
Node* next;
};
/*
Starts at a specified node and then sequentially goes through every following node and outputs the int value of each one
*/
void printLinkedListValues(Node* currentNode) {
while (currentNode != 0) {
cout << currentNode->value << ", ";
currentNode = currentNode->next;
}
}
/*
The main class runs the program. In this case it utilizes the Node class we made and creates four nodes.
*/
int main() {
Node* root = new Node();
Node* secondNode = new Node();
Node* thirdNode = new Node();
Node* fourthNode = new Node();
root->value = 5;
root->next = secondNode;
secondNode->value = 10;
secondNode->next = thirdNode;
thirdNode->value = 15;
thirdNode->next = fourthNode;
fourthNode->value = 20;
fourthNode->next = NULL;
//printing the linked list starting at the root node
printLinkedListValues(root);
return 0;
};
Output:
5, 10, 15, 20
Doubly Linked List
Doubly Linked List
A doubly linked list has a "previous node" variable in addition to the "next node" and "value" variables that a singly linked list has. Knowing both the previous and next nodes gives more functionality to a linked list because you can now traverse both ways and insert/delete easier.
The below code creates methods for node insertion and deletion in the middle of a list. In the next section, we will go over stacks and queues which are lists that use insertion and deletion at the start and end of a list. For simplicity's sake, this code only works for inserting and deleting nodes other than the first or last.
using namespace std;
#include <iostream>
class Node {
public:
int value;
Node* next;
Node* previous;
Node(int v) {
value = v;
}
Node() {}
};
void printDoublyLinkedListValues(Node* currentNode) {
while (currentNode != 0) {
cout << currentNode->value << ", ";
currentNode = currentNode->next;
}
}
void insertIntoList(Node* previousNode, int newValue) {
Node* newNode = new Node(newValue);
newNode->next = previousNode->next;
previousNode->next = newNode;
}
void deleteFromList(Node* nodeName) {
nodeName->previous->next = nodeName->next;
nodeName->next->previous = nodeName->previous;
delete nodeName;
}
int main() {
Node* root = new Node();
Node* secondNode = new Node();
Node* thirdNode = new Node();
Node* fourthNode = new Node();
root->value = 1;
root->previous = 0;
root->next = secondNode;
secondNode->value = 2;
secondNode->previous = root;
secondNode->next = thirdNode;
thirdNode->value = 3;
thirdNode->previous = secondNode;
thirdNode->next = fourthNode;
fourthNode->value = 5;
fourthNode->previous = thirdNode;
fourthNode->next = 0;
cout << "Values before insertion:\n";
printDoublyLinkedListValues(root);
insertIntoList(thirdNode, 4);
cout << "\nValues after insertion\n";
printDoublyLinkedListValues(root);
deleteFromList(thirdNode);
cout << "\nValues after deletion:\n";
printDoublyLinkedListValues(root);
}
Output:
Values before insertion:
1, 2, 3, 5,
Values after insertion
1, 2, 3, 4, 5,
Values after deletion:
1, 2, 4, 5,
Page updated
Google Sites
Report abuse