Linked Lists Flashcards

Flashcards for reviewing linked lists concepts in computer science.

What is a List?

An Abstract Data Type that stores a set of items in a linear order without duplicates.

What are the basic operations for a Doubly Linked List?

Includes add(L, Element e), remove(L, e), search(L, Item k), and size(L).

What is the initial value of the head of a new List?

Initially nil, indicating that the list is empty.

What is the general algorithm for the search(L, k) function?

p = L.head; while(p != nil && p.data != k) p = p.next; return p

What is the algorithm for the add(L, e) function, adding at the front of the list?

e.next = L.head; if(L.head != nil) L.head.prev = e; L.head = e; e.prev = nil

What is the general algorithm for the remove(L, e) function?

if (e.prev != nil) e.prev.next = e.next; else L.head = e.next; if (e.next != nil) e.next.prev = e.prev

What is a Singly Linked List?

A linked list with no prev pointer, can only be traversed in the forward direction.

What are some possible variations in linked list implementations?

Insert and remove at particular position, remove by data, iterators, and sentinels.