Member Avatar for tennis

I am not familiar with linked list, can any one help?

  • 3 Contributors
  • 2 Replies
  • 97 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by griswolf

Dani AI

Generated

Short answer: worst-case search in a plain linked list is linear time. is correct and 's note about average work (~half the nodes) is helpful; the worst case happens when the target is absent or sits at the tail, forcing a full traversal. The root cause is that a linked list only gives pointer-to-next access, not random indexing, so you must follow nodes one by one (Linked list).

Important nuances to keep in mind: if you already hold a pointer to a node, accessing or removing at that node is O(1). A sorted linked list can let you stop early sometimes, but you cannot apply binary search because it needs random access — worst-case remains linear. To get asymptotically faster searches you must add auxiliary structures: skip lists give expected O(log n) search, hash tables give expected O(1) (with worst-case degeneration), and balanced search trees give O(log n) worst-case — each has tradeoffs in memory and update cost (Skip list, Hash table).

Practical advice for C: for small or mostly-sequential workloads a plain list is fine. For frequent value lookups, use an array or a hash map mapping keys to node pointers (handle duplicates with buckets), or use a balanced tree for ordered queries. If you need both fast lookup and cheap insert/remove at known nodes, maintain a list plus an index structure and keep them synchronized.

Recommended Answers

All 2 Replies

Member Avatar for aspire1

O(n)

Member Avatar for griswolf

A linked list is some nodes each of which has a link to the next node (singly linked) or both the next and previous nodes (doubly linked). Each list has a head node, doubly linked lists have a tail node too. Search for an element must proceed from one end until the element is found, so on average you will have to look through half the nodes to find a given element. Let C be 0.5 and O(C*n) is the same as O(n), as aspire1 said. ... but re-reading your post and seeing 'worst case' then let C be 1.0 and you get the same answer anyhow.

Edited by griswolf because: n/a
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.