This week's book giveaway is in the OCAJP forum. We're giving away four copies of OCA Java SE 8 Programmer I Study Guide 1Z0-808 and have Jeanne Boyarsky & Scott Selikoff on-line! See this thread for details.
Hello! Could someone please explain the following statements : • Using a linked list supports insertion, deletion, and growing the store, but makes indexed access slower. • Using a tree supports insertion, deletion, and growing the list, indexed access is slow, but searching is faster. • Using hashing supports insertion, deletion, and growing the store. Indexed access is slow, but searching is particularly fast. However, hashing requires the use of unique keys for storing data elements. What's the difference between indexed access and searching? Thank you! Tina
but makes indexed access slower. indexed access is slow, but searching is faster.Indexed access is slow, but searching is particularly fast.
indexed access means refering to the Nth element of a collection, as in "I want the 9th element of this list". Some collections are fast for this kind of request, others are slow, like linked lists. Searching means, locating a specific object and retrieving it. For example, I could have the key-value pair Fred-Blue, stored in a HashMap, and I want to search for it by key (Fred). Searching for the key retrieves the value , Blue, and is much faster than saying "give me the 9th element in this Map."
Joined: Mar 12, 2002
Thanks Rob! But why is it that using a linked list makes indexed access slower and using a tree makes indexed access slow, but searching is faster? Thanks!!! Tina
Originally posted by Tina Ang: Thanks Rob! But why is it that using a linked list makes indexed access slower and using a tree makes indexed access slow, but searching is faster? Thanks!!! Tina
Well, Jose posted a link to what looks like a good and lengty discussion on the strengths of the different types of collections, but if I understand your question right, you want to know the basic difference between a linked list and a tree? Well, in a college programming course, they usually cover that, but since not everyone who is on this forum has that background, let me see if I can remember the differences. Linked list is like a chain. Each link is connected by pointing to the next link (also points to the previous link if it's a double linked list) Trees as basically left-right paths. Values larger go one way, and values smaller go the other way. It keeps branching off until you hit the end level. So visually, if you have to search, it would look like this: <-><-><-><-><-><-><->
(Sorry for the crude drawing, ASCII art has never been my forte, and hopefully it will look okay) The top is a linked list, and the bottom is a tree (drawn sideways, they are usually drawn going downward). Search for 67 in both and see how many steps it takes you. For more in depth information, you can always search google for things like 'tree algorithm' or 'linked list' and you'll probably hit a billion pages that goes into deep math about how each algorithm performs. [Edited to try and fix the ASCII examples] [ April 04, 2002: Message edited by: Donald Yee ]
Donalds explaination was good.. but let me add to it what I remember for data structures. In a linkedlist you cannot get to a certain number without going threw all the ones before it. The objects in a linkedlist dont actually know where they are, they just know whos in front of them, and sometimes knows whos behind them. So to get to a certain number will call something like nextNode() a certain number of times.. and thats the last call will be the node you want. With things like arrays, they are a set size so when you call to request a certain index, it will just jump to it without the extra calls. Linked lists are good at moving things around. Trees have some of the same problems as LinkedLists. It has to go down the "stems" of the tree to find the index, adding on time. Searching is made faster(SOMETIMES) however because it has the ability to cut out hunks of the search. It can look at two leaves and say.. "Ok, Im bigger than that one, but smaller than that one".. and go the correct route, eliminating the need to go down the other part of the tree.. and therefore looking at less to find its match... Trees are good at speeding up searching.
PS. Just be glad you don't have to program these yourself.. it sucks
In C, a singly-linked list is a series of data structures (or nodes, in this context) linked only by pointers. Data structure A has a pointer that refers to data structure B, which in turn has a pointer to data structure C which in turn has a pointer to... well, you get the picture. C had arrays too, you see, but they were dangerous to use. It was very easy to overwrite past the last element because for one thing, arrays were not objects and they had none of the pleasant convenience of myArray.length, or the reassuring safety of an ArrayIndexOutOfBoundsException. The program wouldn't raise a peep while it was trashing your data. Those were grim days... But anyway, it would be nice if arrays were resizable, hence C had linked lists. To make the footprint small, the pointers had to point only to the next guy and no one else, plus the "main" pointer that pointed to the "head" of the linked list --- the first node. Pointers there had to be, because all the nodes were stored in the heap, thus saving everyone the trouble of passing a local copy of the entire linked list (expensive in terms of memeory) to every function that would mine its riches. Why pass a local copy if you can simply pass a single pointer (worth just a few bytes) referring to the "head" node? Of course, the drawback was, if manage to somehow lose the pointer to the "head" you can kiss your entire linked list goodbye because that single pointer was your only access point. So if you want to get the data in the Nth node, for example, you must first access the "head" node, because only he knows where in the hard disk the second node is, and the second node is the only one who knows where the third node is, etc. Please note, the memory spaces occupied by nodes are not contiguous, unlike arrays. So you have to traverse the linked list from the head to the Nth node, so it's slow. For example, suppose everybody in this thread was a node. That would be: Tina, Rob, Jose, Donald, Joshua and finally me. We're all scattered in different cities, but suppose, Tina had Rob's phone number (and only her), Rob had Jose's, and so on... If somebody wanted to call Joshua, for example, (say Val, or one of the Sheriffs), he had to call Tina who would have to call Rob, and so on. If you want to "insert" another node into our little collective (between Rob and Jose), say Val, all you have to do is change the value of two pointers: Rob's pointer referring to Jose is now referring to Val, and Val's pointer now has to refer to Jose, so the entire linked list is unbroken. Quick and clean... -anthony