a linked list is a concrete data type that is an implementation of a list
characteristics
- is the list sorted? the nodes are sorted by their
key(usually in an ascending order) - is the list doubly/singly linked? in a doubly linked list each node points to the next and previous node whereas in a singly linked list a node only points to the next
- does the list have a tail? a pointer
tail(x)points to the last node in a linked list - is the list circular? in a circular linked list the last node points to the first whereas in a non-circular linked list it points to NULL (nothing)
functions
insert(x): insertsxsearch(k): returns the node whose key iskisEmpty(): returns whether list is emptydelete(x): given the nodex, removes it from the list