Class Notes (1,019,982)
CA (585,699)
U of C (7,233)
CPSC (122)
Lecture 5

CPSC 319 Lecture Notes - Lecture 5: Cengage Learning, Linked List, Geoffrey Chaucer

6 pages110 viewsWinter 2017

Department
Computer Science
Course Code
CPSC 319
Professor
Leonard Manzara
Lecture
5

This preview shows pages 1-2. to view the full 6 pages of the document.
Arrays&and&Linked&Lists&
!
Lists&
- Are!classified!as!linear!data!structures!
- May!be!one-dimensional,!or!multi-dimensional!
- Each!element!of!a!list!might!consist!of:!
o A!single!data!item,!or!
o A!record!or!object!(compound!data)!
- Lists!may!be!ordered!(sorted)!or!unordered!
- A!list!is!an!Abstract!Data!Type!(ADT)!that!supports!these!operations:!
o add(newEntry)
§ Adds!an!item!to!the!end!of!the!list!
o insert(newEntry, position)!
§ Inserts!an!item!into!a!list!at!the!specified!position!
o delete(position)!
§ Deletes!the!item!at!the!specified!position!
o clear()!
§ Deletes!all!items!from!the!list!
o getEntry(position)!
§ Return!the!item!at!the!specified!position!
May!be!done!by!value!or!by!reference!
o replaceEntry(position, newEntry)!
§ Overwrite!the!item!at!the!specified!position!with!a!new!item!
o getLength()!
§ Returns!the!number!of!items!currently!in!the!list!
o isEmpty()!
§ Returns!true!if!no!items!in!the!list,!false!otherwise!
o isFull()!
§ Returns!true!if!the!list!is!full,!false!otherwise!
o display()!
§ Prints!out!all!items!in!the!list!
o contains(itemKey)!
§ Returns!true!if!the!list!contains!the!item,!false!otherwise!
o search(itemKey)!
§ Returns!the!item!that!matches!the!key!(or!nil!if!no!match)!
- Lists!may!be!implemented!in!many!ways!
o E.g.!Arrays,!linked!lists!
o In!RAM,!or!in!secondary!storage!(file!on!disk)!
!
Arrays&
- Are!also!called!physically)ordered)lists!
- Definition:!Are!linear,!random!access!data!structures,!whose!elements!are!accessed!by!a!
unique!identifier!called!an!index!or!subscript!!
- Elements!are!stored!contiguously!in!RAM!or!in!secondary!storage!
- Most!modern!programming!languages!directly!support!arrays!
o Java!example:!int[] array = new int[10];!
You're Reading a Preview

Unlock to view full version

Only half of the first page are available for preview. Some parts have been intentionally blurred.

- Structure:!
o Formal!view:!
!
Set!of!array!elements!!! ! " #$%& $'& $(& ) & $*+!
Mapping!function!! ! ,-....... /.../..../.........../!
Set!of!array!indices! ! .0 " #.1%& .1'& .1(& ) & 1*+!
!
o Programming!language!view:!
!
!!23242567- 82%2'2(8 ) 82*8!!
!
- Languages!like!C,!C++,!and!java!require!indices!to!start!at!0!
o Others,!like!Pascal!and!FORTRAN!are!more!flexible!
- Arrays!are!fixed!in!length:!
o At!compile-time!for!most!languages!
o At!run-time!for!languages!like!Java!
- Imposes!a!maximum!size!for!a!list!
o May!run!out!of!room!as!we!add!items!
o Wastes!space!if!we!use!only!part!of!the!array!
- Inserting!an!item!into!an!array!may!require!shifting!elements!to!make!room!for!it!
o 89:9 ;:<5 =>628?2=28!! ! !
89:9 ...........8;:<5 =>628?2=28!!
!!89:9 @>A:38;:<5 =>628?2=28!!
o Pseudocode:!
!
insert(newEntry, position)
for (i = n-1; i >= position; i--)
array[i+1] = array[i]
array[position] = newEntry
n = n + 1
o Is!BC5D!in!the!worst!case!(inserting!at!position!0)
- Deleting!an!item!may!require!shifting!items!to!fill!the!gap
o 89:9 ;:<5 =>628?2=28!!
8........ ;:<5 =>628?2=28!!
;:<5 =>628?2=28!!
§ Pseudocode:!
!
delete(position)
for (i = position; i < n-1; i++)
array[i] = array[i+1]
n = n - 1
- Is!BC5D!in!the!worst!case!(deleting!at!position!0)
- Accessing!an!item!by!position!is!BCED
o i.e.!Getting!or!replacing!entries!is!very!quick
- Must!use!sequential!search!on!unordered!arrays!
- Can!use!sequential!or!binary!search!on!ordered!arrays!
!
You're Reading a Preview

Unlock to view full version


Loved by over 2.2 million students

Over 90% improved by at least one letter grade.