linked lists the -expressions are formed according to the following recursive rules the atomic symbols etc are -expressions null expression is also admitted if is an -expression so is ( if and are -expressions so is ( -"recursive functions of symbolic expressions, mccarthy list implements an ordered collection of valueswhich may include repetitions sepcificallya singly linked list is data structure that contains sequence of nodes such that each node contains an object and reference to the next node in the list the first node is referred to as the head and the last node is referred to as the tailthe tail' next field is null the structure of singly linked list is given in figure there are many variants of linked listse in doubly linked listeach node has link to its predecessorsimilarlya sentinel node or self-loop can be used instead of null to mark the end of the list the structure of doubly linked list is given in figure list is similar to an array in that it contains objects in linear order the key differences are that inserting and deleting elements in list has time complexity ( on the other handobtaining the kth element in list is expensivehaving (ntime complexity lists are usually building blocks of more complex data structures howeveras we will see in this they can be the subject of tricky problems in their own right figure example of singly linked list the number in hex below node indicates the memory address of that node figure example of doubly linked list for all problems in this unless otherwise statedeach node has two entries-- data fieldand next fieldwhich points to the next node in the listwith the next field of the last node being null its prototype is as followsclass listnode def __init__ (self data = next_node =none)self data data self next next_node