Linked List with Python Built-in List
Last updated on August 19, 2022 pm
Linked List with Python Built-in List
Intro
I was currently reading the Composing Programs, which amazed me over and over again.
In section 2.3.7 Linked Lists, a definition of linked list was introduced by using the python built-in type list
only. It used empty = 'empty'
to suggest the end of the linked list, whereas I plan to use NoneType
to standardize the code.
1 |
|
Construct
Firstly, we need a function to check a given list is a linked list or not:
1 |
|
And naturally, the function link()
can help us wrap up the head
and rest
two part into a new list whose length is 2.
1 |
|
Different from the definition I written in my previous post, this definition generates a linked list from tail side to head. But nothing changed actually. Let’s take a closer look at it.
Notice:
According to this definition, None
is a legal linked list, whereas [None]
is illegal.
This detail could be helpful to the functions coming ahead.
Implementation
We need some useful functions to manipulate our new data type.
1 |
|
Except these functions unwrapping the linked list, we also need to measure it’s length and evaluate the value of arbitrary node.
Iterative
1 |
|
Based on these fuctions, we can preliminarily manipulate our linked list.
Recursive
We can also rewrite our len_link()
and get_item_link()
functions in a recursive manner. This concept will emerge again later and is quite significant.
1 |
|
Abstraction
Append
Next step, we need to append the linked list. It seems that extending a node-form linked list - by simply altering it’s Next
attribute - is handy, while appending the list-form linked list sounds not so intuitive. Well, partially true.
Here is the function from Composing Programs.
1 |
|
This is a quite standard recursive function. And here is the function I typed when I was first conceiving it. To make life much easier, I prefer writing them separately.
1 |
|
Similarly, we can manage any other function with the concepts of higher-order function and recursion.
For example, apply a function to all entries in a linked list.
Apply to all
1 |
|
Conversion
So how to convert a linked list into a normal list? And vice versa?
Inherited from methods above, answers may not be very complicated.
1 |
|
Note
Using python built-in list to form a linked list, this probably is not a vary popular approach, and its efficiency is open to discussion.
However, what truly intriguing here is that even only one data type can be realized in various way. Also, every function in this post can be achieved in diverse manners. The possibilities in programming are always charming and charismatic.
References
- Composing Programs by John DeNero;
- Online Python Tutor;