Pointers and Linked Lists

• Pointers and Linked Lists

Linked Lists

• A linked list is constructed using pointers.
• Linked lists are not always the most efficient storage for data.
• Linked lists allow dynamic sizing, which is a key advantage.
• The first node in a linked list is commonly named 'head'.
• The pointer in the last node of a linked list should point to NULL.
• You cannot directly access the nth node of a linked list.
• The number of possible nodes is determined by the freestore size.
• To add a node, update the pointer variable in the new node first.
• If creating a linked list class, implement the destructor, copy constructor, and the assignment operator.
• You need to include the big three (copy constructor, destructor, and assignment operator) for a linked list class.
• If there are any nodes following the head node when inserting an element via headInsert, they would be lost
• If you need to access the last element of a linked list with N nodes, N comparisons are needed.
• You move 0 nodes to insert an element at the front of a list with N nodes.
• A linked list can be implemented using linked-lists or arrays
• Use a linked list over an array or dynamic array when you do not know the maximum size.
• The pointer in a node points to the whole node.
• To declare a pointer to a node of type MyNode, the correct syntax is MyNode* ptr.
• If declaring a node type struct and typedef a pointer type, declare the node first and then the typedef.
• If you have a node pointer named head pointing to a valid node, access the 'item' member variable using head->item or (*head).item.
• The arrow operator (->) specifies a member of a struct or class that is pointed to by a pointer variable.
• To signify that a pointer variable doesn't point to memory, generally set it to NULL.
• The actual value of NULL is 0.
• The pointer variable 'head' points to the first node in the list.
• NodeTypePtr head; allocates only the memory for a pointer variable.
• 'head -> item = 3' would put the value of 3 in the item part of the first node in the linked list.
• 'head = new Node;' allocates memory for the first item in the list
• The following loop correctly uses iter as an iterator to move through the nodes of the linked list: for( iter=head; iter != NULL; iter=iter->link)

Operators

• The dot operator (.) has higher precedence than *.
• The arrow operator (->) combines dereferencing and dot actions.

Memory

• Dynamically allocated memory that is no longer pointed to by any pointer variable causes a memory leak.

Nodes

• A 'Node' is a struct or class object that has one or more member variables that are pointer variables.
• When adding a node to a linked list the pointer variable in the new node is updated first.

NULL vs nullptr

• C++11 uses 'nullptr' instead of NULL to distinguish between the null value and the number 0.

Stacks and Queues

• A stack is a specialized type of list
• Stacks exhibit last-in/first-out behavior.
• Most applications using a stack store a struct or class object on the stack.
• A queue is first-in-first-out data structure.
• A stack can be implemented using linked-lists or arrays
• A stack exhibits last-in/first-out behavior.
• Push is used to put data into a stack.
• Pop is used to get the data at the top (or front) of the stack.
• Pop removes an item from the stack.
• If you push items 1,4,8,16 onto a stack, 16 is at the top.
• Data is removed from a stack in reverse order to how it was entered.
• Stacks do not resemble a line of people at a bank (First in First Served)
• Pushing onto a stack inserts data at the top.
• Popping involves removing data from a stack.
• Error checking is needed when pushing or popping a stack.
• Data is inserted at the back of a queue.
• Operations for a stack include pop, push, empty.
• Operations for a queue include add, remove, empty.