Friday, 28 February 2014

Understanding Linked List

Stanford CS Education Library: a 26 page  introduction to linked lists in C/C++. Includes examples, drawings, and practice problems, and solution code. The more advanced article,  Linked List Problems, has 18 sample problems with solutions.
This article introduces the basic structures and techniques for building linked lists with a mixture of explanations, drawings, sample code, and exercises. The material is useful if you want to understand linked lists or if you want to see a realistic, applied example of pointer-intensive code. Even if you never really need a linked list, they are an excellent way to learn pointers and pointer algorithms.

Download LinkedListBasics.pdf

A quick review of linked list basics followed by 18 linked list problems, basic through advanced, with solution code in C/C++.  Nobody really uses linked lists any more, so why bother with these problems? Linked lists are a superb source of complex practice problems. Link list problems are simple to define, yet can have complicated, pointer-intensive solutions (which is why they are often used on exams and in interviews). If you are serious about your pointer/algorithm skills, there's no substitute for practice and this is the place to start.For a few problems, multiple solutions are presented, such as iteration vs. recursion or dummy node vs. reference pointer. The problems are: Count, GetNth, DeleteList, Pop, InsertNth, SortedInsert, InsertSort, Append, FrontBackSplit, RemoveDuplicates, MoveNode, AlternatingSplit, ShuffleMerge, SortedMerge, SortedIntersect, Reverse, and RecursiveReverse.

Download LinkedListProblems.pdf