Download LinkedList Problems PDF

TitleLinkedList Problems
TagsPointer (Computer Programming) C (Programming Language) Computer Programming Software Development Computer Data
File Size54.4 KB
Total Pages35
Document Text Contents
Page 1

Linked List
Problems

By Nick Parlante Copyright ©1998-2002, Nick Parlante

Abstract
This document reviews basic linked list code techniques and then works through 18
linked list problems covering a wide range of difficulty. Most obviously, these problems
are a way to learn about linked lists. More importantly, these problems are a way to
develop your ability with complex pointer algorithms. Even though modern languages
and tools have made linked lists pretty unimportant for day-to-day programming, the
skills for complex pointer algorithms are very important, and linked lists are an excellent
way to develop those skills.

The problems use the C language syntax, so they require a basic understanding of C and
its pointer syntax. The emphasis is on the important concepts of pointer manipulation and
linked list algorithms rather than the features of the C language.

For some of the problems we present multiple solutions, such as iteration vs. recursion,
dummy node vs. local reference. The specific problems are, in rough order of difficulty:
Count, GetNth, DeleteList, Pop, InsertNth, SortedInsert, InsertSort, Append,
FrontBackSplit, RemoveDuplicates, MoveNode, AlternatingSplit, ShuffleMerge,
SortedMerge, SortedIntersect, Reverse, and RecursiveReverse.

Contents
Section 1 — Review of basic linked list code techniques 3
Section 2 — 18 list problems in increasing order of difficulty 10
Section 3 — Solutions to all the problems 20

This is document #105, Linked List Problems, in the Stanford CS Education Library.
This and other free educational materials are available at http://cslibrary.stanford.edu/.
This document is free to be used, reproduced, or sold so long as this notice is clearly
reproduced at its beginning.

Related CS Education Library Documents
Related Stanford CS Education library documents...

• Linked List Basics (http://cslibrary.stanford.edu/103/)
Explains all the basic issues and techniques for building linked lists.

• Pointers and Memory (http://cslibrary.stanford.edu/102/)
Explains how pointers and memory work in C and other languages. Starts
with the very basics, and extends through advanced topics such as
reference parameters and heap management.

• Binary Trees (http://cslibrary.stanford.edu/110/)
Introduction to binary trees

• Essential C (http://cslibrary.stanford.edu/101/)
Explains the basic features of the C programming language.

Similer Documents