Share your knowledge at the LQ Wiki.
Go Back > Forums > Non-*NIX Forums > Programming
User Name
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.


  Search this Thread
Old 10-30-2005, 05:30 AM   #1
Registered: Feb 2004
Location: Athens, Greece
Distribution: Gentoo,FreeBSD, Debian
Posts: 705

Rep: Reputation: 30
linked lists: java vs c

In Java, i know i have to go throught the whole list -access it serially- in order to find something.
What about c? Is there a way to achieve a random access? For example, i 'd like to do binary search- after it has been sorted of course.
Old 10-30-2005, 11:50 AM   #2
Registered: Oct 2005
Location: Chicago, USA
Distribution: Slackware & Fedora
Posts: 66

Rep: Reputation: 15
Re: linked lists: java vs c

To achieve random access:
In C, use an array and the qsort function followed by a bsearch.
In C++, use a vector and then sort and binary_search or lower_bound template (I think these are under the algorithms header).

Linked-lists will always take O(n) to locate an element even in sorted order because the chain must still be traversed.
Old 10-30-2005, 03:11 PM   #3
LQ Guru
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
To amplify a bit:

1. Java provides a set of "standard containers": List, Map, etc etc and algorithms to act on them.

2. ANSI C++ provides STL (the "Standard Template Library"): an analogous set of standard data structures and standard methods. STL pre-dates Java containers; STL was template-based from Day One; Java containers only became type-aware with the latest, Java 5.0 release (and .Net containers won't support templates until the upcoming, .Net 2.0 release).

3. C doesn't have any such standard containers or algorithms. But of course, you can create an implement any data structures and algorithms you want in C. Just as you can in C++ and/or Java.

One example is to store your data in an array, do a qsort() to re-order the array, and do bsearch() lookups on the ordered array. Another example would be to implement a binary tree, where the items are (by definition) stored and retrieved in sorted order. And so forth.

4. It should be emphasized that some containers are "random access", and others aren't. Lists and trees, for example, must be traversed. Arrays (aka Vectors) and Maps, on the other hand, permit immediate access and/or direct lookup.

5. And even in Java, C++ and C#, it's often useful to implement your own "container" type.

'Hope that helps .. PSM

Last edited by paulsm4; 10-30-2005 at 05:02 PM.
Old 10-30-2005, 03:24 PM   #4
Senior Member
Registered: Aug 2005
Posts: 1,755

Rep: Reputation: 50
Re: linked lists: java vs c

Originally posted by nocturna_gr
In Java, i know i have to go throught the whole list -access it serially- in order to find something.
What about c? Is there a way to achieve a random access? For example, i 'd like to do binary search- after it has been sorted of course.
You may be using the wrong class. Linked lists ("LinkedList" class in Java, "list" class in C++) by definition don't have random access; in return they allow you to have constant time insertion and deletion in the middle of the list. Whereas if you want random access, you should use vectors ("ArrayList" class in Java, "vector" class in C++), with the drawback that insertion and deletion in the middle is very inefficient. And Java does have a binary search function: Collections.binarySearch() which, if used on a random access list like "ArrayList" which is already sorted, is guaranteed to operate in O(log n).
Old 10-30-2005, 05:41 PM   #5
Registered: Mar 2004
Location: Massachusetts
Distribution: Debian
Posts: 557

Rep: Reputation: 42
It might be worth mentioning that glib (distinct from glibc) has some generic containers like linked lists, trees, and hashes for C. The lack of a standard container library is still annoying though..


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
Linked Lists leonidg Programming 7 03-10-2005 03:07 AM
queue and linked lists Palamides Programming 2 03-09-2005 09:08 PM
Linked Lists - What and Why? scuzzman Programming 9 12-31-2004 11:51 AM
c++ doubly linked lists durden2.0 Programming 4 02-25-2004 06:56 PM
c++ linked lists jclark00001 Programming 10 02-23-2003 03:40 PM > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 01:29 PM.

Main Menu
Write for LQ is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration