Editing Adjacency list (section)

==Implementation details==
{| class = "wikitable" align="right" style="width:18em;"
| colspan = "3" | The graph pictured above has this adjacency list representation:
|-
| a || adjacent to || b,c
|-
| b || adjacent to || a,c
|-
| c || adjacent to || a,b
|}

An adjacency list representation for a graph associates each vertex in the graph with the collection of its neighbouring vertices or edges. There are many variations of this basic idea, differing in the details of how they implement the association between vertices and collections, in how they implement the collections, in whether they include both vertices and edges or only vertices as first class objects, and in what kinds of objects are used to represent the vertices and edges.
* An implementation suggested by [[Guido van Rossum]] uses a [[hash table]] to associate each vertex in a graph with an [[array data structure|array]] of adjacent vertices. In this representation, a vertex may be represented by any hashable object. There is no explicit representation of edges as objects.<ref>{{cite web
 |last         = van Rossum
 |first        = Guido
 |author-link  = Guido van Rossum
 |year         = 1998
 |title        = Python Patterns — Implementing Graphs
 |url          = https://www.python.org/doc/essays/graphs/
 |access-date  = 2014-08-17
 |archive-date = 2016-06-25
 |archive-url  = https://web.archive.org/web/20160625055021/https://www.python.org/doc/essays/graphs/
 |url-status   = live
}}</ref>
* Cormen et al. suggest an implementation in which the vertices are represented by index numbers.<ref>{{cite book
  | last1 = Cormen |first1=Thomas H. |authorlink1 = Thomas H. Cormen
  | last2 = Leiserson |first2=Charles E. |authorlink2 = Charles E. Leiserson
  | last3 = Rivest |first3=Ronald L. |authorlink3 = Ronald L. Rivest
  | last4 = Stein |first4=Clifford |authorlink4 = Clifford Stein
  | title = [[Introduction to Algorithms]], Second Edition
  | publisher = MIT Press and McGraw-Hill
  | year = 2001
  | isbn = 0-262-03293-7
  | pages = 527–529 of section 22.1: Representations of graphs
  }}</ref> Their representation uses an array indexed by vertex number, in which the array cell for each vertex points to a [[singly linked list]] of the neighboring vertices of that vertex. In this representation, the nodes of the singly linked list may be interpreted as edge objects; however, they do not store the full information about each edge (they only store one of the two endpoints of the edge) and in undirected graphs there will be two different linked list nodes for each edge (one within the lists for each of the two endpoints of the edge).
*The [[object oriented]] incidence list structure suggested by Goodrich and Tamassia has special classes of vertex objects and edge objects. Each vertex object has an instance variable pointing to a collection object that lists the neighboring edge objects. In turn, each edge object points to the two vertex objects at its endpoints.<ref name="A">{{cite book
  | last1 = Goodrich |first1 = Michael T. |author-link1 = Michael T. Goodrich
  | last2 = Tamassia |first2 = Roberto |author-link2 = Roberto Tamassia
  | title = Algorithm Design: Foundations, Analysis, and Internet Examples
  | publisher = John Wiley & Sons
  | year = 2002
  | isbn = 0-471-38365-1}}</ref> This version of the adjacency list uses more memory than the version in which adjacent vertices are listed directly, but the existence of explicit edge objects allows it extra flexibility in storing additional information about edges.