there are two types of list-related problems--those where you have to implement your own listand those where you have to exploit the standard list library we will review both these aspects herestarting with implementationthen moving on to list libraries implementing basic list api--searchinsertdelete--for singly linked lists is an excellent way to become comfortable with lists search for keydef search_list (lkey)while and data !keyl next if key was not present in the list will have become null return insert new node after specified nodeinsert new_node after node def insert_after (node new_node )new_node next node next node next new_node delete nodedelete the node past this one assume node is not tail def delete_after (node)node next node next next insert and delete are local operations and have ( time complexity search requires traversing the entire liste if the key is at the last node or is absentso its time complexity is ( )where is the number of nodes list problems often have simple brute-force solution that uses (nspacebut subtler solution that uses the existing list nodes to reduce space complexity to ( very oftena problem on lists is conceptually simpleand is more about cleanly coding what' specifiedrather than designing an algorithm consider using dummy head (sometimes referred to as sentinelto avoid having to check for empty lists this simplifies codeand makes bugs less likely it' easy to forget to update next (and previous for double linked listfor the head and tail algorithms operating on singly linked lists often benefit from using two iteratorsone ahead of the otheror one advancing quicker than the other table top tips for linked lists know your linked list libraries we now review the standard linked list librarywith the reminder that many interview problems that are directly concerned with lists require you to write your own list class under the hoodthe python list type is typically implemented as dynamically resized arrayand the key methods on it are described on page this is concerned specifically with