Explain the Cursor implementation of linked list?

Answer 1

The only difference between a link list and the cursor implementation of a linked list is that the curse implementation makes it a link list with different linked node methods. A cursor implementation of linked list involves using several nodes with the "next" pointer going to the index to trigger another node in the list.

Answer 2

A linked list is a data container that defines a data sequence. The data elements of a linked list are typically stored in non-contiguous memory, thus we cannot traverse from one element to the next as we can with a dense container like an array. To keep track of an element we use a node. A node is a simple data structure with a pointer that refers to the data it is keeping track of. In some cases it may be more convenient or efficient to store the data within the node itself but in most cases we use a pointer. In addition, a node also has another pointer which refers to the next node in the sequence (or the null address if it is the last node in the sequence, the tail node). In this way we need only keep track of the head node. A node to keep track of a type T data element may be defined as follows:

struct node {

T* data; // pointer to the data element (of type T)

node* next; // pointer to next node in the sequence (if any)

};

To locate a data element we simply traverse the sequence of nodes from the head node. For example we can search for a given value as follows:

node* find (node* head, T value) {

while (head != nullptr) {

if (head->data == value) return head; // found it!

head = head->next;

}

return nullptr; // the value does not exist

}

A singly-linked list only allows forward traversal and is therefore known as a forward list. A forward list is usually optimised for short lists or lists that are frequently empty. In particular, a forward list does not maintain a count of its nodes. This allows more efficient insertion and extraction of the data elements.

A doubly-linked list is a list where every node has two links, one to the next element and one to the previous element. This time we keep track of both the head and tail and can traverse the list in both directions. A doubly-linked list is ideally suited to longer lists and will typically maintain a count of its nodes.

A circular linked list is a list where the tail node links "forwards" to the head node. Instead of keeping track of the head we keep track of the tail, because the tail gives us constant time access to the head. This then allows us to insert more efficiently at both the head and tail of the list (with a non-circular list, insertions are efficient at the head, not the tail).

If the circular linked list is doubly linked, the head also links "backwards" to the tail node thus we can either keep track of the head or the tail to keep track of both.

Inserting before the head or after the tail is a constant time operation provided we have constant time access to the head or the tail. Inserting anywhere else takes linear time because we must traverse to the insertion point. Once the insertion point is established, we simply copy the previous node's next link into the new node's next link, before replacing it with the new node's address. With doubly-linked lists, we also copy the next node's previous link into the new node's previous link, and replace it with the new node's address.

Answer 3

Some languages do not support pointers. Use arrays of objects instead start with a Freelist.Allocate space from Freelist when needed to delete: change pointers, add to Freelist