![]() This is because the insert method, no matter what, will always take the same amount of time: it can only take one data point, it can only ever create one node, and the new node doesn’t need to interact with all the other nodes in the list, the inserted node will only ever interact with the head. ![]() Technically you can insert a node anywhere in the list, but the simplest way to do it is to place it at the head of the list and point the new node at the old head (sort of pushing the other nodes down the line).Īs for time complexity, this implementation of insert is constant O(1) (efficient!). This insert method takes data, initializes a new node with the given data, and adds it to the list. ![]() The head argument will default to None if a node is not provided.) class LinkedList(object): (Note: the linked list doesn’t necessarily require a node to initialize. When the list is first initialized it has no nodes, so the head is set to None. ![]() The first architectural piece of the linked list is the ‘head node’, which is simply the top node in the list. Search: searches list for a node containing the requested data and returns that node if found, otherwise raises an errorĭelete: searches list for a node containing the requested data and removes it from list if found, otherwise raises an error My simple implementation of a linked list includes the following methods: These will come in handy when we implement the Linked List. We also add a few convenience methods: one that returns the stored data, another that returns the next node (the node to which the object node points), and finally a method to reset the pointer to a new node. The node initializes with a single datum and its pointer is set to None by default (this is because the first node inserted into the list will have nothing to point at!). class Node(object):ĭef _init_(self, data=None, next_node=None): Along with the data each node also holds a pointer, which is a reference to the next node in the list. The node is where data is stored in the linked list (they remind me of those plastic Easter eggs that hold treats). For example, if the list initially allocates enough space for eight nodes, on the ninth insertion the list will have to double its allocated space to 16 and copy over the original 8 nodes, a more expensive operation than a normal insertion. * In practice this means certain insertions are more expensive. The main advantage of using a linked list over a similar data structure, like the static array, is the linked list’s dynamic memory allocation: if you don’t know the amount of data you want to store before hand, the linked list can adjust on the fly.* Of course this advantage comes at a price: dynamic memory allocation requires more space and commands slower look up times. The nodes in a doubly linked list will contain references to both the next node and the previous node). In its most basic form, a linked list is a string of nodes, sort of like a string of pearls, with each node containing both data and a reference to the next node in the list (Note: This is a singly linked list. But eight whirlwind weeks were not enough to solidify these concepts, so I thought it’d be beneficial, both for my own edification and for other budding Pythonistas, to write a series on basic data structures, starting with the linked list. A lot of self-taught programmers don’t realize the importance of these concepts until they already have an interview lined up, and by then it’s already too late! I was fortunate enough to attend the Code Fellows Python Development Accelerator, where a section of the curriculum was dedicated to basic data structures and algorithms.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |