Data Structures at Birkbeck College, University Of London | Flashcards & Summaries

Lernmaterialien für Data structures an der Birkbeck College, University of London

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Data structures Kurs an der Birkbeck College, University of London zu.

TESTE DEIN WISSEN

Data structures

Lösung anzeigen
TESTE DEIN WISSEN

Data structures are containers that organize and group data together in different ways. 


When you write code to solve a problem, there will always be data Involved - and how you store or structure that data in the computer's memory can have a huge impact on what kinds of things you can do with it and how efficiently you can do those things

Lösung ausblenden
TESTE DEIN WISSEN

What are some important considerations when inserting or deleting elements from a linked list?

Lösung anzeigen
TESTE DEIN WISSEN

If you delete the next reference and replace it with a new object, you will lose the old reference, so you should always assign your pointer for the newly inserted element before you assign your pointer for three previous elemnt so you do not lose your reference to the old one.

Lösung ausblenden
TESTE DEIN WISSEN

How can you implement a stack data structure using an array?

Lösung anzeigen
TESTE DEIN WISSEN

...

Lösung ausblenden
TESTE DEIN WISSEN

Two common types of queues

Lösung anzeigen
TESTE DEIN WISSEN

Dequeues

Priority queues

Lösung ausblenden
TESTE DEIN WISSEN

Lists

Lösung anzeigen
TESTE DEIN WISSEN
  • Have an order, so you can say things like "give me the 3rd item in the list"
  • Have no fixed length, so you can add or remove elements to/from whichever location in the list.

Think for example of a shopping list, a list of students, a list of the things in your house.

It therefore might contain objects of different types.

Lösung ausblenden
TESTE DEIN WISSEN

Array insertion and deletion time complexity.

Lösung anzeigen
TESTE DEIN WISSEN

You would need to go through each element in the array as you would need to re-index each element after the newly inserted/deleted item.  Worst case is O(n)

Lösung ausblenden
TESTE DEIN WISSEN

What types of linked lists do you know?

Lösung anzeigen
TESTE DEIN WISSEN

Singly linked lists

doubly-linked lists

Circular lists

Lösung ausblenden
TESTE DEIN WISSEN

Append

Lösung anzeigen
TESTE DEIN WISSEN

Adding something at the end.

Lösung ausblenden
TESTE DEIN WISSEN

Linked List append time complexity

Lösung anzeigen
TESTE DEIN WISSEN

Appending something to the end of a linked list is done in linear time O(n) because, since you are tracking the head only, you will need to iterate through the whole list to find the tail

Lösung ausblenden
TESTE DEIN WISSEN

Linked-list time complexity

Lösung anzeigen
TESTE DEIN WISSEN

prepending (adding to the head of the list) can be done in constant 𝑂(1) time.

Lösung ausblenden
TESTE DEIN WISSEN

When is a linked list considered pathological?

Lösung anzeigen
TESTE DEIN WISSEN

A circular linked list is typically considered pathological because when you try to iterate through it, you'll never find the end. We usually want to detect if there is a loop in our linked lists to avoid these problems

Lösung ausblenden
TESTE DEIN WISSEN

Stacks

Lösung anzeigen
TESTE DEIN WISSEN

Stacks are list-based data structures but are different from arrays and linked lists. 

A stack is a last in first out data structure.

With an array, we can access any element from the array using its index. With a stack, we can only access things from one end of the collection/list.

With a stack, you have a container and you can only access its objects from one end of the container, you cannot add or remove things from the middle or from the bottom.

Lösung ausblenden
  • 440 Karteikarten
  • 59 Studierende
  • 0 Lernmaterialien

Beispielhafte Karteikarten für deinen Data structures Kurs an der Birkbeck College, University of London - von Kommilitonen auf StudySmarter erstellt!

Q:

Data structures

A:

Data structures are containers that organize and group data together in different ways. 


When you write code to solve a problem, there will always be data Involved - and how you store or structure that data in the computer's memory can have a huge impact on what kinds of things you can do with it and how efficiently you can do those things

Q:

What are some important considerations when inserting or deleting elements from a linked list?

A:

If you delete the next reference and replace it with a new object, you will lose the old reference, so you should always assign your pointer for the newly inserted element before you assign your pointer for three previous elemnt so you do not lose your reference to the old one.

Q:

How can you implement a stack data structure using an array?

A:

...

Q:

Two common types of queues

A:

Dequeues

Priority queues

Q:

Lists

A:
  • Have an order, so you can say things like "give me the 3rd item in the list"
  • Have no fixed length, so you can add or remove elements to/from whichever location in the list.

Think for example of a shopping list, a list of students, a list of the things in your house.

It therefore might contain objects of different types.

Mehr Karteikarten anzeigen
Q:

Array insertion and deletion time complexity.

A:

You would need to go through each element in the array as you would need to re-index each element after the newly inserted/deleted item.  Worst case is O(n)

Q:

What types of linked lists do you know?

A:

Singly linked lists

doubly-linked lists

Circular lists

Q:

Append

A:

Adding something at the end.

Q:

Linked List append time complexity

A:

Appending something to the end of a linked list is done in linear time O(n) because, since you are tracking the head only, you will need to iterate through the whole list to find the tail

Q:

Linked-list time complexity

A:

prepending (adding to the head of the list) can be done in constant 𝑂(1) time.

Q:

When is a linked list considered pathological?

A:

A circular linked list is typically considered pathological because when you try to iterate through it, you'll never find the end. We usually want to detect if there is a loop in our linked lists to avoid these problems

Q:

Stacks

A:

Stacks are list-based data structures but are different from arrays and linked lists. 

A stack is a last in first out data structure.

With an array, we can access any element from the array using its index. With a stack, we can only access things from one end of the collection/list.

With a stack, you have a container and you can only access its objects from one end of the container, you cannot add or remove things from the middle or from the bottom.

Data structures

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten Data structures Kurse im gesamten StudySmarter Universum

Otganisational Structure

University of Groningen

Zum Kurs
Structural Analysis

Hellenic Open University

Zum Kurs
Cell Structure

Silliman University

Zum Kurs
Prokaryotic Cell Structure

Cagayan State University

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Data structures
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Data structures