Linked List Basics

Linked List

Basics

By Nick Parlante Copyright © 1998-2001, Nick Parlante

Abstract

This document 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. A separate document, Linked List Problems (http://cslibrary.stanford.edu/105/), presents 18 practice problems covering a wide range of difficulty.

Linked lists are useful to study for two reasons. Most obviously, linked lists are a data structure which you may want to use in real programs. Seeing the strengths and weaknesses of linked lists will give you an appreciation of the some of the time, space, and code issues which are useful to thinking about any data structures in general.

Somewhat less obviously, linked lists are great way to learn about pointers. In fact, you may never use a linked list in a real program, but you are certain to use lots of pointers. Linked list problems are a nice combination of algorithms and pointer manipulation. Traditionally, linked lists have been the domain where beginning programmers get the practice to really understand pointers.

Audience

The article assumes a basic understanding of programming and pointers. The article uses C syntax for its examples where necessary, but the explanations avoid C specifics as much as possible — really the discussion is oriented towards the important concepts of pointer manipulation and linked list algorithms.

Other Resources

• Link List Problems (http://cslibrary.stanford.edu/105/) Lots of linked list problems, with explanations, answers, and drawings. The "problems" article is a companion to this "explanation" article.

• Pointers and Memory (http://cslibrary.stanford.edu/102/) Explains all about how pointers and memory work. You need some understanding of pointers and memory before you can understand linked lists.

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





This is document #103, Linked List Basics, 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.





Contents

Section 1 — Basic List Structures and Code  2 Section 2 — Basic List Building  11 Section 3 — Linked List Code Techniques  17 Section 3 — Code Examples  22

Edition

Originally 1998 there was just one "Linked List" document that included a basic explanation and practice problems. In 1999, it got split into two documents: #103 (this document) focuses on the basic introduction, while #105 is mainly practice problems. This 4-12-2001 edition represents minor edits on the 1999 edition.

Dedication

This document is distributed for free for the benefit and education of all. That a person seeking knowledge should have the opportunity to find it. Thanks to Stanford and my boss Eric Roberts for supporing me in this project. Best regards, Nick -- nick.parlante@cs.stanford.edu

Section 1 — Linked List Basics

Why Linked Lists?

Linked lists and arrays are similar since they both store collections of data. The terminology is that arrays and linked lists store "elements" on behalf of "client" code. The specific type of element is not important since essentially the same structure works to store elements of any type. One way to think about linked lists is to look at how arrays work and think about alternate approaches.

Array Review

Arrays are probably the

...