不要求,讲数据结构时,参考一下。

 

In computer science, a linked list is a linear collection of data elements, in which linear order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a group of nodes which together represent a sequence

Singly-linked-list.svg

Linked list operations

The following code inserts a node after an existing node in a singly linked list. The diagram shows how it works. Inserting a node before an existing one cannot be done directly; instead, one must keep track of the previous node and insert a node after it.

CPT-LinkedLists-addingnode.svg
 function insertAfter(Node node, Node newNode) // insert newNode after node
     newNode.next := node.next
     node.next    := newNode

Inserting at the beginning of the list requires a separate function. This requires updating firstNode.

 function insertBeginning(List list, Node newNode) // insert node before current first node
     newNode.next   := list.firstNode
     list.firstNode := newNode

Similarly, we have functions for removing the node after a given node, and for removing a node from the beginning of the list. The diagram demonstrates the former. To find and remove a particular node, one must again keep track of the previous element.

CPT-LinkedLists-deletingnode.svg
 function removeAfter(Node node) // remove node past this one
     obsoleteNode := node.next
     node.next := node.next.next
     destroy obsoleteNode
 function removeBeginning(List list) // remove first node
     obsoleteNode := list.firstNode
     list.firstNode := list.firstNode.next // point past deleted node
     destroy obsoleteNode

You have no rights to post comments