How do the different types

How do the different types

of linked lists compare?

I. Introduction:

a. As you may recall from previous tutorials, linked lists offer a variety of benefits.

i. We can order elements without having to physically sort them.

ii. We can order on any fields, or any number of fields.

iii. We can establish and maintain link lists without extreme efforts.

iv. We can develop search procedures on linked lists which can significantly reduce the number of comparisons needed to find an element.

II. Purpose of Tutorial

a. The purpose of this tutorial is to emphasize the differences among the three types of linked lists:

i. Singly Linked Lists

ii. Doubly Linked Lists

iii. Leveled Linked Lists

III. Singly Linked Lists

a. Singly linked lists have several advantages:

i. Allow for display in order without sorting.

ii. Can order on any field.

iii. Easy to establish and maintain.

iv. Need not search until list end if an element is not on the lists.

b. This is self-explanatory. For example:

i. Say we have a database containing the information of four students at a public library.

ii. For every student we have 4 fields, the table below provides the bytes used for every field.

Field

Name

Address

ID #

Books Checked Out

Data Type

Char [25]

Char [40]

Char[10]

Int

Pointer

Bytes

iii. Now we know that we need (81*3) 243 contiguous bytes of storage.

c. NOTE that we use the field Next to use as a pointer, and this is what makes this link list a Singly Link List.

d. If we want to sort the Name field by alphabetical order using pointers, it would look like this:

Address	Field	Name	Address	ID #	Books Checked Out	next
1000	0	Damien, Mac	123 Renoir	987665	5	1162
1081	1	Oreo, Simone	3948 Diego Rivera	234953	10	NULL
1162	2	Graham, Mah	2349 Picasso	234959	7	1081
1243	3	Ahoy, Chip	4935 Van Gogh	432535	1	1000

e. Having this link list, there is no need to store the Name field alphabetically, the pointers will do all the work for you!

f. Also, if you are searching a name on this link list, the program will look for it and it will automatically stop after it found it.

g. Unfortunately, Singly Link Lists also have disadvantages:

i. Sequential Search Only

ii. Search in One Direction

IV. Doubly Link Lists

a. Doubly Linked Lists offers the same advantages that are listed for Singly Link Lists. An additional advantage that Doubly Linked Lists offers are:

i. Search & Display in both Directions

ii. Still Easy create/update

b. Doubly Linked Lists offers the pointer next, and also an extra pointer called previous.

i. Previous pointer allows users to do their search in the opposite direction of next.

ii. *NOTE: You will need 4 extra bytes of storage for the pointer Previous.

c. For example: In the following table, if you were doing an alphabetical search and your target was Oreo, the system would start from bottom-up.

i. It would be the 1^stitem on the list, and the search would stop.

ii. If this was the case for Singly Linked Lists, the search would start with Ahoy, and move down until Oreo was found.

Next Previous

Address	Field	Name	Address	ID #	Books Checked Out	next	previous
1000	0	Damien, Mac	123 Renoir	987665	5	1170	1255
1085	1	Oreo, Simone	3948 Diego Rivera	234953	10	NULL	1170
1170	2	Graham, Mah	2349 Picasso	234959	7	1085	1000
1255	3	Ahoy, Chip	4935 Van Gogh	432535	1	1000	NULL