Data Structures in Programming (Arrays and Linked Lists)?

Question

What is the average number of nodes accessed in searching for a particular element in an unordered list? In an ordered list? In an unordered array? In an ordered array?

Is there a difference between linear search in a linked list and an array?

The best answer will receive more points than usual.

Answer 1

1. unordered list: list length / 2, if unordered means random. Ordered list: same. Unordered array: same. Ordered array: less, if doing a binary search or similar efficient (non-linear) strategies, but it depends on the strategy, and none has been specified.



2. No, not in terms of how many nodes are accessed, if they're sorted the same way.

Answer 2

A LinkedList ONLY works because insertions and deletions are done in sort order.



An array is always faster because the references are unique (indexed). There is a penalty for sorting before the search. The LinkedList is maintaining the pointers for you and has a small penalty in initializing node 'previous' and node 'next'. On LinkedList those pointers are unknown until accessed.



There is no data integrity without sorting. None.



I cannot see the question: 'number of nodes accessed...' that would be based on criteria, eg. find Employee by Surname and then FirstName.

Answer 3

The number searched depends on the search algorithm. there's no "average" with an unknown algorithm. (The "average" for all algorithms combined is meaningless - it has 0 correlation to the real world.)