Linked list

From CS 61A Wiki
Revision as of 21:57, 30 June 2014 by Sunseth (Talk | contribs)


Jump to: navigation, search

A linked list is a recursive data structure. It consists of a series of nodes. Each node has two placeholders, denoted first and rest.

Types of linked lists

In a straight-forward linked list, a node's first placeholder contains a value (String, number, ect), while the second placeholder will contain another linked list. Using this structure, a series of nested linked lists can form a list of values. A deep linked list is slightly different. The first and second placeholder in a deep linked list contain another linked list. A good way to visualize linked lists is to draw them out.

Linked list methods

In order to traverse and manipulate a linked list, the user must utilize linked list methods. The first function takes a linked list as its argument and returns the first element of that linked list. The rest function takes a linked list as its argument and returns the remainder of the argument linked list, which is the smaller linked list that comprises the rest of the argument linked list.

Examples

Sources