CS 121 Lecture Notes - Lecture 79: Doubly Linked List, Linked List
5 Jul 2018
School
Department
Course
Professor
Dynamic Representations:
An array is only 1 way in which a list can be represented.
Arrays are limited in one sense b/c they have a fixed size throughout their
existence.
oSometimes we don’t know how big to make an array b/c we don’t know
how much info we will store.
The ArrayList class handles this by creating a larger array &
copying everything over whenever necessary.
This is not necessarily an efficient implementation.
Dynamic Data Structure: implemented using links.
oUsing references as links between objects, programmers can create
whatever type of structure is appropriate for the situation.
oIf implemented carefully, structure can be quite efficient to search &
modify.
oStructures created this way are considered to be dynamic b/c their size is
determined dynamically, as they are used, & not by declaration.
Dynamic List Representation:
oA programmer can use different list implementations, depending on the
specific needs of the program they are designing.
EX: In some situations, it may make processing easier to implement a
doubly linked list in which each node has not only a reference to the
next node in the list, but another reference to the previous node in the
list.
class Node
{
int info;
Node next, prev;
}
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
An array is only 1 way in which a list can be represented. Arrays are limited in one sense b/c they have a fixed size throughout their existence: sometimes we don"t know how big to make an array b/c we don"t know how much info we will store. The arraylist class handles this by creating a larger array & copying everything over whenever necessary. This is not necessarily an efficient implementation. Dynamic list representation: a programmer can use different list implementations, depending on the specific needs of the program they are designing. Like a single linked list, the next reference of the last node is null. The previous node of the first node is null since there"s no node that comes before the first one. This type of structure makes it easy to move back & forth between nodes in the list. This also requires more effort to set up & modify: header node:
