DEV Community

Cover image for Introduction to Data Structures and Algorithms With Python

Introduction to Data Structures and Algorithms With Python

Jeff Odhiambo on February 18, 2022

This article is a continuation of Python 101: Introduction to Modern Python where we introduced, set up and gave some basic understanding of the py...
Collapse
 
darkwiiplayer profile image
𒎏Wii 🏳️‍⚧️

I'm kind of confused; why do you list linked lists as non-linear, but then you have trees and graphs as examples for non-linear structures? Also, by your definitions, maps wouldn't fall into either category.


 The costly operation is inserting or deleting the element from the beginning of the List

In the ages of CPU cache, this needs lots of asterisks and disclaimers

Collapse
 
smartjeff profile image
Jeff Odhiambo • Edited

linked list is linear and I listed it as linear, and explained that in linear data structures are data structures structures where data are accessed siquentially. kindly check again.

About insertion and deletion operation, they are expensive in the sence that much time can be taken as it may involve shifting of elements where a certain order is to be maintained

Collapse
 
darkwiiplayer profile image
𒎏Wii 🏳️‍⚧️

yes but linked lists are trees though (and, by extension, graphs)

Thread Thread
 
Sloan, the sloth mascot
Comment deleted
 
darkwiiplayer profile image
𒎏Wii 🏳️‍⚧️

That's... factually incorrect. Have you even looked up the definition of trees before writing an article on them?

Thread Thread
 
smartjeff profile image
Jeff Odhiambo • Edited

hope this will help in understanding why one is linear and why the other is non linear
dev-to-uploads.s3.amazonaws.com/up...

Thread Thread
 
darkwiiplayer profile image
𒎏Wii 🏳️‍⚧️ • Edited

But... linked lists are literally trees though; they can't be linear and non-linear at the same time 😂

EDIT: That image is nice, but wrong. Trees are just (connected) graphs without loops, so every linked list is also a tree.

Thread Thread
 
darkwiiplayer profile image
𒎏Wii 🏳️‍⚧️

I'll just quote wikipedia here:

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.

Which perfectly applies to a linked list:

  • Any two list elements are connected by exactly one path
  • There are no loops in a list

There's even a whole programming language that pretty much implements linked lists as a special case of binary trees (That's lisp I'm talking about), and you could easily do the same in any other programming language that implements trees.

Thread Thread
 
smartjeff profile image
Jeff Odhiambo

I think we are also learning new stuffs in the process, maybe the resources that I was using in my research were not clear 😅. And they have given me a new Friend called DarkWiiPlayer

Thread Thread
 
darkwiiplayer profile image
𒎏Wii 🏳️‍⚧️

Yaaay!

By the way it may seem like a technicality but it's actually a really cool thing. So many things can be thought of as special kinds of graphs so learning a thing or two about those can be immensely helpful in so many programming problems 😁

Thread Thread
 
tylerroost profile image
tylerroost

So we agree that linked lists are both linear and non linear. And when using the definition of seuqnetiality would a tree not be linear because there is topological ordering from the root to leaves?

Thread Thread
 
smartjeff profile image
Jeff Odhiambo

that's more clear, thanks

Collapse
 
shivamkumarsah profile image
Shivam Kumar Sah

Linked list and an Array both are Linear, there shouldn't be a confusion about it.
Tree data structure can be constructed by the help of Linked List.
Also A linked list has previous / Next variable while a Tree have left right, the idea is To maintain linked list in linear order(left to right) while for tree it should be in Hirerchial order, (top to down)

Collapse
 
darkwiiplayer profile image
𒎏Wii 🏳️‍⚧️

I think you are confusing the general concept of a Tree with the more specific concept of a Binary Tree.

Tree nodes don't have left and right, they simply have descendants. Just as a Binary tree is a specific form of tree where every node has exactly two descendants (left and right), you can define a unary tree where every node has exactly one descendant, which happens to be exactly what a linked list is.

Put more simply: Take a linked list and turn it around by 90 degrees. What do you get? A tree.

Collapse
 
brayan_kai profile image
Brayan Kai

Great article here 👏👏🥳 Keep the good work up

Collapse
 
smartjeff profile image
Jeff Odhiambo

Thanks Kai 🤝🏻

Collapse
 
owino profile image
Owino

Great article.

Collapse
 
smartjeff profile image
Jeff Odhiambo

Thanks @owino

Collapse
 
rothman857 profile image
rothman857

FYI python has a built in package called Queue. No need to implement queues and stacks with lists. Queue supports LIFO, FIFO, and priority.

Collapse
 
smartjeff profile image
Jeff Odhiambo

Agreed, but was just showing how to implement a queen with a list, thanks

Collapse
 
rothman857 profile image
rothman857

Also, you should mention Dataclasses and NamedTuples. Both are very useful built-in packages for storing data.

Collapse
 
smartjeff profile image
Jeff Odhiambo

am going to consider them in my next article which will be a continuation of this