A linked list is a data structure that uses an ordered collection of nodes in random storage.

computer science

Description

Introduction 

A linked list is a data structure that uses an ordered collection of nodes in random storage. In a doubly linked list, each node holds the value entered at that position plus a link to the node just before it and node just after it in the collection. A circular doubly linked list would have the next reference of the last node link to the first node and the previous reference of the first node link to the last. Normally a doubly linked list maintains a reference to the first node and the last node. For a circular list, maintaining a reference to just the first node is sufficient. However, in an endless circular doubly linked list the concept of first or last is meaningless, as is the concept of indices. Instead, the linked list maintains a reference to the current node. This reference is known as the cursor. Insertion happens either just before or just after the current node and removal happens only at the current node. The user finds items by either searching forward or back from the current position.


The following operations are possible: 

• addPrev(value) – adds the value right before the current one and moves the cursor to the new node, or if cursor is null make the value the cursor 

• addNext(value) – adds the value right after the current one and moves the cursor to the new node, or if the cursor is null make the value the cursor 

• remove() – removes the current value and returns it, moving the cursor to the next node or setting it to null if the last value was removed 

• getValue() – returns the current value but does not remove it 

• setValue(value) – changes the current value to the given one, returning true if successful and false if not (if currentNode is null) 

• getPrev() – moves the cursor back one node and returns that value 

• getNext() – moves the cursor forward one node and returns that value 

• moveToNext(value) – moves the cursor forward until it finds the value or circles back to the same place, returning true if the value was found, including at the current node, or false if not 

• moveToPrev(value) – moves the cursor backwards until it finds the value or circles back to the same place, returning true if the value was found, including at the current node, or false if not


Related Questions in computer science category