CreateList(),createsandreturnsanew,emptylist.
• InsertListNode(L,p,n),addsnodenafternodepinlistL.Ifpisnull,then we insert n as the new head of the list. The function returns a pointer to n. We assume that the node n has already been created with some data that we want to add in the list. We will not get into the details on how nodes are actually created. Briefly, some memory must be allocated and initialized, so that the node contains the data we want and a pointer. InsertListNode then needs only change pointers. It must make the pointer of n point to the next node, or to null, if p was the last node of the list. It must also change the pointer of p to point to n, if p is not null.
• InsertInList(L, p, d), adds a node containing d after node p in list L. If p is null, then we insert the new node as the new head of the list. The function returns a pointer to the newly inserted node. The difference with InsertListNode is that InsertInList creates the node that will contain d, whereas InsertListNode takes an already created node and inserts it in the list. InsertListNode inserts nodes, whereas InsertInList inserts data contained in nodes it creates. That means that InsertInList can use InsertListNode to insert in the list the node it creates.
RemoveListNode(L, p, r), removes node r from the list and returns that node; p points to the node preceding r in the list, or null if r is the head. We will see that we need to know p in order to remove the item pointed by r efficiently. If r is not in the list, it returns null.
• RemoveFromList(L, d), removes the first node containing d from the list and returns the node. The difference with RemoveListNode is that it will search the list for the node containing d, find it, and remove it; d does not point to the node itself; it is the data contained inside the node. If there is no node containing d in the list, RemoveFromList returns null.
• GetNextListNode(L, p), returns the node following p in list L. If p is the last node in the list, then it returns null. If p is null, then it returns the first node of L, the head. The returned node is not removed from the list.
• SearchInList(L, d), searches the list L for the first node containing d. It returns the node, or null if no such node exists; the node is not removed from the list.
