Downloaded 13 times
Uploaded byBianca Teşilă
Data structures and algorithms lab6
This document discusses linked lists and their implementation and operations. It covers: - The basics of linked lists and how they are implemented differently than dynamic arrays. Linked lists have nodes that point to the next element, while arrays reallocate size as needed. - Common linked list operations like add, remove, get, and update elements, which work differently based on implementation. - Types of linked lists including singly and doubly linked linear and circular lists. - An exercise to separate the elements of a linked list into two lists based on even and odd elements. - Homework to create a task list application using a linked list to store and remove tasks by priority.
Data structures and algorithms lab6
- 1. DATA STRUCTURES ANDALGORITHMS LAB 6 Bianca Tesila FILS, March 2014
- 2.
- 3. LINKED LISTS: INTRODUCTION What is a list? What is a linked list?
- 4. LISTS: IMPLEMENTATION LinkedLists Each node contains the information and the link to its neighbors (doubly linked lists) or to the next element in the list (singly linked lists ) The nodes are allocated dynamically Dynamic Arrays The nodes are stocked in arrays If, when adding a new element, the size of the array is exceeded, the array is reallocated What are the advantages and disadvantages of each implementation?
- 5. LISTS: BASIC OPERATIONS oAdd – adds an element (entity) to the list: at the beginning, at the end or at an arbitrary position o Remove – removes an element (entity) from the beginning/end of the list or by taking into account its index/content o Get – retrieves an element by taking into account its index o Update – updates the information/content of an element !! These operations depend on the chosen implementation.
- 6. LINKED LISTS: TYPES Singly-linked linear lists Doubly-linked linear lists
- 7. LINKED LISTS: TYPES Singly-linked circular lists Doubly-linked circular lists
- 8. LINKED LISTS !!Exercise: Taking intoaccount the elements of a linked list, store them in two separate linked lists - one for the even elements and another one for the odd elements.
- 9. HOMEWORK Imagine youhave a task list. Each task has a priority and a description. You would like to solve these tasks according to their priority. Whenever you solve a task, you remove it from the list. Implement an application for managing a task list using a linked list.