What's the difference between the data structure List and Graph?

Question

I know that singly linked lists are made of nodes where each node has a pointer to the next node (or null to end the list), but graphs also have nodes with data and pointers to the next.

So what's the essential difference between the data structure Linked List and Graph? And how about the List-based search and Graph-based search?

Answer 1

Linked List and Graph has similarities but the linked list nodes are rigid. The nodes of linked list has predefined structure but nodes in graph do not have predefined structure, for examples one node of a graph can have any number of connection to the other node but the list node has predefined connections. The list node can only connect to the same type of node but the graph node can be connected to different type of node as well.

Answer 2

It is not true, linked list also have data in it's nodes!(why do you want to have a list of nodes without any information?), In fact from mathematical view a linked list is some sort of graph.

The main difference between graph in general and linked list is that a node in linked list could at most have two pointers(one to its next and one to its previous node) but a node in graph could have more than two pointers.

Answer 3

Linked list is data structure in computer science and graph is math abstraction. Linked list is one of possible implementations of graph. You can always implement graph in a different way. For example graph with n vertices can be implemented as an array[n][n] where if array[i][j] is true then there is an edge from vertex i to vertex j.
There are different implementations of linked list too. You can keep link to previous and next node, or just to one of them. But it will be a node with link to another node, because it's definition of linked list. Definition of graph doesn't say anything about how to keep it in computer program.