answersLogoWhite

0

You compare items in a linked list by searching for them. Iterate through the list, comparing elements with the search key. If you encounter end-of-list, then the key is not found, otherwise you have found the element desired. Note that this is a half linear search. Statistically, if an element is to be found, it will be found at the halfway point, assuming uniformly random distribution of data. In the worst case, if the element is not found, it will always take a full search to prove that. You could keep the linked list in order, by inserting each element before the element that has higher key value. This would reduce search time to half, because searching would stop with the element with higher key value. Searching is not a very efficient use of a linked-list. It would be better to use some kind of ordered list, perhaps a dynamic array with binary search, or a balanced binary tree, which has similar search performance but one with the most cost to design and implement. Linked-lists are better for keeping elements in the order they were encountered or inserted, such as processing tokens in a compiler. Sorry, but every solution has its tradeoffs.

User Avatar

Wiki User

15y ago

What else can I help you with?

Continue Learning about Engineering

Convert single linked list to double linked list?

You copy a singly linked list into a doubly linked list by iterating over the singly linked list and, for each element, calling the doubly linked list insert function.


Why you use linked list instead of arrays?

You would use linked lists instead of arrays in two instances: 1) You don't know how long your list will be and it is apt to dramatically change length. 2) You will make lots of additions and removals in the middle of your list.


What is the difference between linked list and Ordinary list?

A list is an abstract data structure, usually defined as an ordered collection of data. A linked list refers to a specific implementation of a list in which each element in the list is connected (linked) to the next element.


W difference between a linear linked list and a circular linked list?

Oh, dude, a linear linked list is like a straight line where each element points to the next one, while a circular linked list is like a loop-de-loop rollercoaster where the last element points back to the first one. So, in a linear list, you reach the end and it's like hitting a wall, but in a circular list, you just keep on looping around for eternity. It's like the difference between a dead-end street and a roundabout.


What is difference between linked list and singly linked list?

Answersingly linked list has the node inserted only at one end. and the pointer corresponds to the next pointer.but in a doubly linked list, the node pointer points to the both previous and the next node.singly linked list has two nodesdoubly linked list has three nodesA doubly linked list makes sense when you need to traverse the list in both directions. You aren't able to do that with a singly linked list.

Related Questions

What is linked list in C langauage?

A linked list is a collection of items, often nodes, that are sequentially linked by some kind of index or pointer contained within each item.


Convert single linked list to double linked list?

You copy a singly linked list into a doubly linked list by iterating over the singly linked list and, for each element, calling the doubly linked list insert function.


Which is the easy insertion operator single linked-list or double-linked list?

It is easier to insert into a singly linked list.


Why you use linked list instead of arrays?

You would use linked lists instead of arrays in two instances: 1) You don't know how long your list will be and it is apt to dramatically change length. 2) You will make lots of additions and removals in the middle of your list.


What is the difference between linked list and Ordinary list?

A list is an abstract data structure, usually defined as an ordered collection of data. A linked list refers to a specific implementation of a list in which each element in the list is connected (linked) to the next element.


W difference between a linear linked list and a circular linked list?

Oh, dude, a linear linked list is like a straight line where each element points to the next one, while a circular linked list is like a loop-de-loop rollercoaster where the last element points back to the first one. So, in a linear list, you reach the end and it's like hitting a wall, but in a circular list, you just keep on looping around for eternity. It's like the difference between a dead-end street and a roundabout.


What is non-integer linked list?

Linked list of strings, for example.


What is the difference between doubly linked list and circular linked list?

A doubly linked list is a linked list in which each node knows where both of its neighbors are.A circular linked list is a linked list in which the "tail" of the list is linked to the "root". (Note that both the tail and root of the list are undefined/arbitrary in a circular linked list)Doubly linked lists are actually not necessarily related to circular linked list (aside from both being based on a linked list structure). In fact, you can have a circular doubly linked list, where each node knows where both of its neighbors are andwhere the list wraps around to connect to itself.


What is difference between linked list and singly linked list?

Answersingly linked list has the node inserted only at one end. and the pointer corresponds to the next pointer.but in a doubly linked list, the node pointer points to the both previous and the next node.singly linked list has two nodesdoubly linked list has three nodesA doubly linked list makes sense when you need to traverse the list in both directions. You aren't able to do that with a singly linked list.


Where linked list using?

linked list are used for creation of stack,queues to use memory in optimum manner linked list are used as they are dynamic in nature


Which of the following data structures can be randomly accessed giving loc A. linked list implemented using array B. singly linked list C. double linked list D. both single and double linked list?

Which of the following data structures can be randomly accessed giving loc?A. linked list implemented using arrayB. singly linked listC. double linked listD. both single and double linked listThe answer is A.


How the pointer used in the linked list?

The pointer in linked list is used for traversing through the elements of the linked list. In a singly linked list, only a next pointer exits. So this pointer can be used for traversing only in one direction in the list. In case of a doubly linked list, a next and previous pointer exits. These pointers are used for traversing in both direction in the list.