List: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 12: Line 12:
A '''linked list''' is a data structure implementing a [[Data Structures#Dynamic_Set|dynamic set]] in which the elements are arranged in a linear order. The order is determined by pointers maintained by elements to other elements in the list. All [[Data Structures#Dictionary|dictionary]] operations (INSERT, DELETE, SEARCH) can be implemented for a list.
A '''linked list''' is a data structure implementing a [[Data Structures#Dynamic_Set|dynamic set]] in which the elements are arranged in a linear order. The order is determined by pointers maintained by elements to other elements in the list. All [[Data Structures#Dictionary|dictionary]] operations (INSERT, DELETE, SEARCH) can be implemented for a list.


A '''simply linked list''' has elements that maintain a ''next'' pointer to the next element in the list. The last element's ''next'' pointer contains NULL.
A '''simply linked list''' has elements that maintain a ''next'' pointer to the next element in the list. The last element's ''next'' pointer contains NULL. A '''doubly linked list''' has elements that maintain a ''next'' pointer to successor in the list and a ''prev'' pointer to the predecessor in the list.
 
A '''doubly linked list''' has elements that maintain a ''next'' pointer to successor in the list and a ''prev'' pointer to the predecessor in the list.


The first element of a list is called '''head''' and the last element is called '''tail'''. For a doubly linked list, the ''head.prev'' is NULL, and for all linked lists, ''tail.next'' is NULL.
The first element of a list is called '''head''' and the last element is called '''tail'''. For a doubly linked list, the ''head.prev'' is NULL, and for all linked lists, ''tail.next'' is NULL.


A list is said to be '''sorted''' if the linear order of the list corresponds to the linear order of keys stored in the elements of the list.
A list is said to be '''sorted''' if the linear order of the list corresponds to the linear order of keys stored in the elements of the list. A '''circular list''' is a list whose head's ''prev'' pointer points to the tail, and the tail's ''next'' pointer points to the head.
 
A '''circular list''' is a list whose head's ''prev'' pointer points to the tail, and the tail's ''next'' pointer points to the head.


=Array List=
=Array List=

Revision as of 23:11, 11 August 2018

Internal

Overview

A list is an implementation of a dynamic set.

Linked Lists

A linked list is a data structure implementing a dynamic set in which the elements are arranged in a linear order. The order is determined by pointers maintained by elements to other elements in the list. All dictionary operations (INSERT, DELETE, SEARCH) can be implemented for a list.

A simply linked list has elements that maintain a next pointer to the next element in the list. The last element's next pointer contains NULL. A doubly linked list has elements that maintain a next pointer to successor in the list and a prev pointer to the predecessor in the list.

The first element of a list is called head and the last element is called tail. For a doubly linked list, the head.prev is NULL, and for all linked lists, tail.next is NULL.

A list is said to be sorted if the linear order of the list corresponds to the linear order of keys stored in the elements of the list. A circular list is a list whose head's prev pointer points to the tail, and the tail's next pointer points to the head.

Array List