代写代考 Linked Lists...

Linked Lists…
An introduction to creating dynamic data structures

Linked Lists definition

• Example of the common use of “list”:
• Read task description
• Design test data
• Create makefile
• Collect other files needed • Begin working on code
• Type in first version

Linked Lists definition
• More formal definition:
::== Nothing | element
• Examples – [nothing]
– element element
– element element element
• Example where “element” is an integer – [nothing]
– 12,15,19,-22,0,54

Linked Lists and pointers
• Theword“list”suggestsanorderedcollection • Theword“linked”hintsatpointerstowhere
the next element in the list is located
– This is different from arrays, which use contiguous memory locations
– Linked lists may use multiple links to link elements according to different interpretations of “order”.
– We will only consider “singly linked lists” for now. 4

Linked Lists memory diagrams
• Alistofthenumbers[0,12,-4,22]
• Anarrayofthenumbers[0,12,-4,22]
• Wherearearraysstored? – Global/static/extern/const? – Stack?
• Wherearelinkedlistsstored?

Linked Lists: Internals
• Thedynamicnatureofthelinkedlistdata structure means we must allocate and free memory on demand
• Somelanguagesdothisforyou.
• NotsoforC
– you have to do it explicitly.

Linked Lists: Internals
struct node {
void *data;
struct node *next;

Linked Lists: Internals
Here is a high-level schematic of a linked list.
A pointer enables us to reference its 1st element.

Three distinctive parts of the list – what are they?

Linked Lists: Internals
Each element in our singly-linked list has two components:
– the data component • anything you want…
– the link component • a pointer, of course!

Linked Lists: Internals
Q: How might a Linked List be terminated? Pointer A: By our “old friend”, the NULL pointer…
Data 0 Element 0
Data 1 Element 1
Data 2 Element 2

Linked Lists: Internals
struct node {
struct node *next;
struct node n; n.data = 0; n.next = NULL;

Linked Lists: Internals
Adding an element to the front of the list.
Data Element 0
Data Element 1
Data Element 2

Linked Lists: Internals
New links are forged by simple assignment
operations.
Q: What happens if we change the order? A: Ooops!
Data 0 Element 0
Data 1 Element 1
Data 2 Element 2

Linked Lists: Internals
Using “boxes and arrows” to show what we are doing with pointers is very helpful…
But it is easy to lose sight of one simple thing:
One pointer can only point to one thing!
Every time we “draw an arrow” we effectively erase any existing arrow coming from that box.
In the previous example we “lost” the linked list because we neglected this!

Linked Lists: Internals
Adding an element elsewhere.
Data Element 1
Data Element 0
Data Element 2

Characteristics of Linked Lists

Characteristics of Linked Lists
What is the worst-case situation for altering the n-th element of:
– an array?
Altering an element anywhere in the array has the same cost. Arrays elements are referred to by their address offset and have O(1) cost.
– a linked list?
Altering an element to the end of the linked list is more costly as the list has to be traversed. The cost
is therefore O(n).

Characteristics of Linked Lists
Advantages of linked lists:
• Dynamicnatureofthedatastructure
• Flexiblestructure – singly linked lists – doubly linked
– circular lists

Characteristics of Linked Lists
Disadvantages of linked lists:
• Linearworst-casecostofaccess
– Skip lists
• TheabsenceofaLinkedListimplementation in standard C libraries
– Build your own

Programming Linked Lists
The dynamic nature of the data structure means we must allocate and free memory *
– malloc()
• to allocate memory when we add an element
• to de-allocate memory when we remove an element

Programming Linked Lists
The element we will use for the example:
”Hello” struct List *next;
struct List { char *content;
Could be anything, of course!!
Note the self-referential nature of the24 pointer; it points to one of these structures.

Programming Linked Lists
Adding an element to the front of the list.
struct List *addToFront(struct List *listp, struct List *newp)
newp->next = listp; return newp;
Draw memory diagrams for:
empty list; list with one element; list with three elements.

List *newp
Return this pointer
List *listp
struct List *addToFront(struct List *listp, struct List *newp) {
newp->next = listp;
return newp;

Programming Linked Lists
Adding an element to the end of the list.
struct List *addToEnd(struct List *listp, struct List *newp) {
struct List *p;
if (listp == NULL)
return newp;
for (p = listp; p->next != NULL; p = p->next)
; /* null statement */ p->next = newp;
return listp;

Programming Linked Lists
Draw pictures of case of empty list *listp

struct List *addToEnd(struct List *listp, struct List *newp) {
struct List *p;
for (p = listp; p->next != NULL; p = p->next) ;
if (listp == NULL) return newp;
p->next = newp;
return listp; }
List *newp
Return this pointer
List *listp

Programming Linked Lists
Draw pictures of case of list *listp containing 2 elements

struct List *addToEnd(struct List *listp, struct List *newp) {
struct List *p;
if (listp == NULL)
return newp;
for (p = listp; p->next != NULL; p = p->next)
p->next = newp; return listp;
List *listp
List *newp

Programming Linked Lists
De-allocating a complete list
void freeAll(List *listp) {
struct List *p;
for ( ; listp != NULL; listp=p) {
p = listp->next; free(listp->content); free(listp);
/* the string */

Programming Linked Lists
Draw the memory diagram for a multi element list.

void freeAll(struct List *listp) { struct List *p;
for ( ; listp != NULL; listp = p ) { p = listp->next; free(listp->content); free(listp);
List *p NULL
List *listp
char * List *
char * List *

Programming Linked Lists
Write a function that deletes the first element in a list.
struct List * deleteFirst(struct List *listp) {
struct List *p;
if (listp != NULL) {
p = listp;
listp = listp->next; free(p);
return listp; }

Programming Linked Lists
Write a function that counts the number of elements in a list.
int count(struct List *listp) {
int cnt = 0;
for ( ; listp != NULL; cnt++)
listp = listp->next;
return cnt; }

üTo extend understanding of pointers by using them to create dynamic data structures
üUnderstand when to use a Linked List
üBe able to create a Linked List in C üunderstand internals
ü be able to program them!

– http://www.club101.org/graphics/imagepic.gif

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts