Linked lists: the basics

Why

We have seen why dynamic memory allocation is necessary, and how to allocate memory dynamically using dynamic arrays:

When we run out of room in a dynamic array, we just copy over the elements to a larger array.

So we can accommodate a virtually unlimited number of elements in a dynamic array.

But dynamic arrays are not right in every situation.

•They leave a lot of space unused, especially when there are several dynamic arrays in a program.

Needed: A way that our program can store the elements without leaving a lot of space unused.

Answer: A linked list, where each element needs room for an extra pointer, but no other memory needs to be left unused.

An advantage of linked lists is that several lists can share a single region of memory:

Another advantage is that elements can be taken off of one list and put onto another by just changing pointers, without copying memory.

Terminology

linked list

A list consisting of items in which each item "knows the location of" (i.e.,contains a pointer to) the next item.

node

An item on a linked list. Each node contains a piece of list data and the location of the next node (item).

next

(in a node) A reference to the next node.

first

A reference that points to the first node.

Linked-list operations

The pseudocode for the algorithms uses these terms

  • first: pointer to the first list item (first node).
  • data: node data
  • next: node link
  • null: pointer that is not an actual address
  • p:reference to a node

Operations:

  1. Create an empty list.

first = null /
  1. Determine whether a list is empty

if (first == null)
// list is empty

  1. Determine whether an item (x) ison a list

p = first
while p is not null and p.datais not x
examine p.data
p = p.next

  1. Add an item (x) to a list. Let p be a reference to a new node with x as data.
  • x goes at the front
    p.data= x
    p.next=first
    first= p

  • x goes at the middle or end. (This pseudocode assumes the list is ordered.)
    The algorithm uses two pointers:current and previous

p.data = x
current = first
while current is not nulland current.data < x
previous = current
current = current.next
if current is first
p.next = first
first = p
else
previous.next = p
p.next = current
endif

  1. Remove an item from a list
    (Change the link of the previous node to point to the node after the current node, or null, if there is no node after the current node. Then, destroy the current node)
    current = first
    while current is not nulland current.datais not x
    previous = current
    current = current.next

if current is not null
if current points to the first node
first = current.next
if current does not point to the first node
previous.next = current.next

When coding linked-list algorithms, always look at these special cases:
  • Empty list
  • List with one element
  • Activity at the beginning of the list
  • Activity at the end of the list
  • Activity that will not occur (e.g., the item is not in the list)

CSC 210 Lecture Notes Lecture 21: Linked lists: the basicsPage 1