CS计算机代考程序代写 data structure INTRO TO COMPUTER SCIENCE II

INTRO TO COMPUTER SCIENCE II
LINKED LISTS
CS162

Data Structures
A particular way of organizing data in a computer so that it can be used effectively
Some examples  Array
 Linked List
 Binary Tree
 Heap

Linear Data Structures
Data structure where elements are arranged sequentially or linearly
Elements are attached to the previous and next elements
Single level
 Can traverse through all elements in a single run through
 Examples  Array
 Stack
 Queue
 Linked list

Linked Lists
A series of connected nodes, where each node is a data structure Nodes are dynamically allocated and deleted
More complex than arrays
Recall STL linked lists
 – doubly linked list, each element has pointers that point at the next and previous elements in the list; no random access
 – singly linked list, each element has a pointer to the next element in the list; no random access
Why wouldn’t we just use vectors?

Linked Lists
Why wouldn’t we just use vectors?  Linked lists are faster
 Easier to insert/delete elements
Cons of linked lists
No random access
 Extra memory space for a pointer is required for element

Linked List Structure
Each node contains data members and pointer  “Reference” or “successor” pointer
The head points to the first node The last node points to null

Linked List Structure
Need a datatype for the node
Can use a struct or class depending on your
implementation
 Self-referential data type/structure
Need a class for managing the nodes
struct node{
int value
node *next;
};
class LinkedList{
private:
node *head
public:
LinkedList(){
head=NULL; }
};

Linked List Structure
Inserting nodes  At the front
 Make a new node
 Put in data
 Set next of new node as head  Set head to point at new node
struct node{
int value
node *next;
};
class LinkedList{
private:
node *head;
public:
LinkedList(){
head=NULL; }
};

Linked List Structure
Inserting nodes  In the middle
 Check if previous node is NULL
 Make a new node
 Put in data
 Set next of new node as next of previous node  Set next of previous node to point at new node
struct node{
int value
node *next;
};
class LinkedList{
private:
node *head;
public:
LinkedList(){
head=NULL; }
};

Linked List Structure
Inserting nodes  At the end
 Make a new node
 Put in data
 Set next of new node as NULL
 Set next of last node to point at new node
struct node{
int value
node *next;
};
class LinkedList{
private:
node *head;
public:
LinkedList(){
head=NULL; }
};

Linked List Structure
Deleting nodes
 Find previous node of the node to be deleted  Change the next of previous node
 Free memory for the node to be deleted
struct node{
int value
node *next;
};

Linked Lists
How would we find the length of a linked list?

Linked Lists
How would we find the length of a linked list?
 Iteration
 Set of instructions repeatedly executed
 for loops
 Stops based on iteration limit
 Recursion
A function calls itself one or more times
 Functions
Stops based on a base case