Linked list: Difference between revisions

Revision as of 12:33, 5 December 2016

Programming basics^[1]

In computer science, a linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing efficient insertion or removal from arbitrary element references ^[2].

In an array we are usually concerned about 2 things, the position (or the index) of an element and the element.

Students should be able to sketch diagrams illustrating: adding a data item to linked list, deleting specified data item, modifying the data held in the linked list, searching for a given data item.

singly linked list[edit]

This video discusses the C programming language, but the content is clear to describe linked list.

doubly linked lists[edit]

This video discusses the C programming language, but the content is clear to describe linked list.

Standards[edit]

Describe how linked lists operate logically.
Sketch linked lists (single, double and circular).

References[edit]

[1] ttp://www.flaticon.com/

[2] ttps://en.wikipedia.org/wiki/Linked_list

[1]

[2]

@@ Line 1: / Line 1: @@
 [[file:arrows.png|right|frame|Programming basics<ref>http://www.flaticon.com/</ref>]]
-Arrays are a fundamental data structure, and they are extremely useful. We use arrays to hold values of the same type at contiguous memory locations. In particular, the use of arrays allows us to create "groups" or "clusters" of variables without needing to give a unique variable name to each, but still allowing us to individually index into the elements of the array. If you haven't started counting from zero yet, now is the time, because in C, arrays are zero-indexed which means the first element of a k-element array is located at array index 0 and the last element is located at array index k-1. In case you're wondering, that's the primary reason we count from 0 in CS50 (and in computer science more broadly!)<ref>http://cs50.wiki/Arrays+and+strings</ref>
+In computer science, a linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing efficient insertion or removal from arbitrary element references <ref>https://en.wikipedia.org/wiki/Linked_list</ref>.
 In an array we are usually concerned about 2 things, the '''position''' (or the index) of an element and the element.
@@ Line 7: / Line 7: @@
 [[File:DataStructuresLinkedList.png]]
+Students should be able to sketch diagrams illustrating: adding a data item to linked list, deleting specified data item, modifying the data held
+in the linked list, searching for a given data item.
 == singly linked list ==