Question? Leave a message!




Linked Lists & Arrays

Linked Lists & Arrays
Dr.MasonHanks Profile Pic
Dr.MasonHanks,Germany,Teacher
Published Date:23-07-2017
Website URL
Comment
CIS 190: C/C++ Programming Lecture 5 Linked Lists 1 Outline • (from last class) Memory and Functions • Linked Lists & Arrays • Anatomy of a Linked List – Details On Handling headPtr • Using Linked Lists – Creation – Traversal – Inserting a Node – Deleting a Node 2 • Homework 4B Memory and Functions • how do different types of variables get passed to and returned from functions? • passing by value • passing by reference – implicit: arrays, strings – explicit: pointers 3 Memory and Functions • some simple examples: int Add(int x, int y); int answer = Add(1, 2); void PrintMenu(void); PrintMenu(); int GetAsciiValue(char c); int ascii = GetAsciiValue (‘m’); • all passed by value 4 Memory and Functions • passing arrays to functions void TimesTwo(int array, int size); int arr ARR_SIZE; / set values of arr / TimesTwo(arr, ARR_SIZE); • arrays of any type are passed by reference – changes made in-function persist 5 Memory and Functions • passing arrays to functions void TimesTwo(int array, int size); void TimesTwo(int array, int size); • both of these behave the same way – they take a pointer to: • the beginning of an array • an int – that we (can) treat like an array 6 Memory and Functions • passing strings to functions void PrintName(char name); void PrintName(char name ); char myName NAME_SIZE = “Alice”; PrintName(myName); • strings are arrays (of characters) – implicitly passed by reference 7 Memory and Functions • passing pointers to int to functions void Square(int n); int x = 9; Square(&x); • pass address of an integer (in this case, x) 8 Memory and Functions • passing int pointers to function void Square(int n); int x = 9; int xPtr = &x; Square(???); • pass ??? 9 Memory and Functions • passing int pointers to function void Square(int n); int x = 9; int xPtr = &x; Square(xPtr); • pass xPtr, which is an address to an integer (x) 10 Memory and Functions • returning pointers from functions CAR MakeCar(void) CAR temp; return &temp; • temp is on the stack – so what happens? 11 Memory and Functions • returning pointers from functions CAR MakeCar(void) CAR temp; return &temp; • temp is on the stack – so it will be returned to the process when MakeCar() returns 12 Memory and Functions • returning pointers from functions CAR MakeCar(void) CAR temp; temp = (CAR) malloc (sizeof(CAR)); return temp; • temp is on the heap – so what happens? 13 Memory and Functions • returning pointers from functions CAR MakeCar(void) CAR temp; temp = (CAR) malloc (sizeof(CAR)); return temp; • temp is on the heap – so it belongs to you and will remain on the heap until you free() it 14 Outline • (from last class) Memory and Functions • Linked Lists & Arrays • Anatomy of a Linked List – Details On Handling headPtr • Using Linked Lists – Creation – Traversal – Inserting a Node – Deleting a Node 15 • Homework 4B What is a Linked List? 16 What is a Linked List? • data structure • dynamic – allow easy insertion and deletion • uses nodes that contain – data – pointer to next node in the list • this is called singly linked, and is what we’ll be using 17 Question • What are some disadvantages of arrays? • not dynamic – size is fixed once created – you can resize it, but you have to do it by hand – same for insertion & deletion; it’s possible, but it’s difficult and there’s no built-in function for it • require contiguous block of memory 18 Question • Can we fix these with linked lists? How? • not dynamic – linked lists can change size constantly – can add nodes anywhere in a linked lists – elements can be removed with no empty spaces • require contiguous block of memory – only one node needs to be held contiguously 19 Question • Are there any disadvantages to linked lists? • harder to search/access than arrayz • need to manage size/counter for size • harder to manage memory – in-list cycles, segfaults, etc. • pointer to next node takes up more memory 20