Transcript Linked Lists and Project 3

Linked List/Project 3
ENEE150 – 0102
ANDREW GOFFIN
Intro to Linked Lists
 Essentially a more dynamic array!
Goffin – ENEE150
Some Linked List Vocab
 Node
 Each element in the list: stores data and a “next pointer”
 Head pointer
 Points to first element in the linked list
 Is NULL for an empty list
 Next pointer
 Pointer in each node that indicates the next node in the list
 Is NULL for the last element in the list
 Tail pointer (if applicable)
 Points to last element in the linked list
 Is NULL for an empty list
Goffin – ENEE150
Defining a linked list
 Use a struct to define a single node in the list
typedef struct node_type{
// type of data depends on application!
int data1;
float data2;
// NEXT POINTER, SUPER IMPORTANT
struct node_type *next;
} node, *pnode;
Goffin – ENEE150
Starting a linked list
int main(void){
pnode head = NULL;
head = (pnode)malloc(sizeof(node));
head->next = NULL;
}
 A single node is allocated
 Next pointer is NULL, indicating that the node is the
last (and only) node in the list
Goffin – ENEE150
Project 3
 Music server
 Use dynamic data structures to store album, user, and playlist
data
Goffin – ENEE150
Project 3 - Albums
 Each album is a structure, and all albums can be
stored as an array of structures

Each structure has three fields:
num_tracks – number of tracks on the album
 tracks – array that stores track names
 playlist_hits – array that stores number of hits each track gets

Goffin – ENEE150
Project 3 – User Accounts
 A linked list of “account” structures
 Add accounts dynamically to list
 Each structure has an ID number, playlist linked list (see in
two slides), and next pointer
 The head pointer to the user’s playlist is what is stored in the
struct – should be initialized to NULL
Goffin – ENEE150
Appending to linked lists
 The last node in a linked list always has its next
pointer set to NULL
 Simple concept: move through next pointers until you
get to one that is NULL, and set that equal to your
new node
 Example: append.c
Goffin – ENEE150
Project 3 - Playlists
 Playlists are linked lists whose head pointers are in
user structs
 Playlist struct has three fields:



album – stores album ID for track
track_num – track number on that particular album
next pointer for linked list
 Can retrieve track name using album, track_num,
and the album array!
Goffin – ENEE150
Other Project 3 Information
 You will take command line arguments for this
project




An “album” file and a “transaction” file
The former stores album data, the latter stores “transaction”
data
Transactions include: printing albums, modifying playlists,
creating user accounts, etc.
Each transaction has a particular transaction ID
Goffin – ENEE150