Difference between revisions of "Linked Lists - Lists"
(Added basic deffinition) |
|||
| (4 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | A linked list is a list where each value is aware of the data that comes before and after the value. | + | =Linked List= |
| + | A linked list is a list where each value is aware of the data that comes before and after the value. | ||
| + | |||
| + | This is achieved by each node having a data value to store the data and a pointer value to point to the next item in the list. We will also need to have a pointer to identify the start of the list. | ||
| + | |||
| + | [[File:Linked list.png]] | ||
| + | |||
| + | To add an item into the linked list: | ||
| + | *you can put the new data into a current space | ||
| + | *find the value it needs to go after and copy the pointer value | ||
| + | *set this pointer value so it points to the new item | ||
| + | *set the pointer of the new value to the copied pointer value | ||
| + | |||
| + | To delete an item from the linked list: | ||
| + | *Find the item you wish to delete | ||
| + | *Copy the pointer value of this item | ||
| + | *Find the item which points to the item to delete | ||
| + | *Replace the pointer value of this item to the copied value | ||
| + | |||
| + | =Expanded Version= | ||
| + | You could have two lists, one is a list of the available spaces within the structure, and the other is the actual list of values to store. | ||
| + | |||
| + | This way you will know the first available space without the need to search for it. Two pointers are need for the list, one for the start of the list and one for the start of the free spaces. | ||
Latest revision as of 10:41, 4 October 2018
Linked List
A linked list is a list where each value is aware of the data that comes before and after the value.
This is achieved by each node having a data value to store the data and a pointer value to point to the next item in the list. We will also need to have a pointer to identify the start of the list.
To add an item into the linked list:
- you can put the new data into a current space
- find the value it needs to go after and copy the pointer value
- set this pointer value so it points to the new item
- set the pointer of the new value to the copied pointer value
To delete an item from the linked list:
- Find the item you wish to delete
- Copy the pointer value of this item
- Find the item which points to the item to delete
- Replace the pointer value of this item to the copied value
Expanded Version
You could have two lists, one is a list of the available spaces within the structure, and the other is the actual list of values to store.
This way you will know the first available space without the need to search for it. Two pointers are need for the list, one for the start of the list and one for the start of the free spaces.
