Menu
What are the main differences between a Linked List and a BinarySearchTree? Is BST just a way of maintaining a LinkedList? My instructor talked about LinkedList and then BST but did't compare them or didn't say when to prefer one over another. This is probably a dumb question but I'm really confused. I would appreciate if someone can clarify this in a simple manner.
898
Using a BST is quite better than a linked list or array. The only advantage of using an array over a BST is the BigO(n) that arrays give when accessing an element. We can use BST as an efficient data structure to store and search for data.
A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.
Unlike Array and Linked List, which are linear data structures, tree is hierarchical (or non-linear) data structure. If we organize keys in form of a tree (with some ordering e.g., BST), we can search for a given key in moderate time (quicker than Linked List and slower than arrays).
Linked List:
Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7) Binary tree:
Node(1) / Node(2) / \ / Node(3) RootNode(4) \ Node(5) \ / Node(6) \ Node(7) In a linked list, the items are linked together through a single next pointer. In a binary tree, each node can have 0, 1 or 2 subnodes, where (in case of a binary search tree) the key of the left node is lesser than the key of the node and the key of the right node is more than the node. As long as the tree is balanced, the searchpath to each item is a lot shorter than that in a linked list.
Searchpaths:
------ ------ ------ key List Tree ------ ------ ------ 1 1 3 2 2 2 3 3 3 4 4 1 5 5 3 6 6 2 7 7 3 ------ ------ ------ avg 4 2.43 ------ ------ ------ By larger structures the average search path becomes significant smaller:
------ ------ ------ items List Tree ------ ------ ------ 1 1 1 3 2 1.67 7 4 2.43 15 8 3.29 31 16 4.16 63 32 5.09 ------ ------ ------ A Binary Search Tree is a binary tree in which each internal node x stores an element such that the element stored in the left subtree of x are less than or equal to x and elements stored in the right subtree of x are greater than or equal to x.
Now a Linked List consists of a sequence of nodes, each containing arbitrary values and one or two references pointing to the next and/or previous nodes.
22
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
