Main Page Modules Alphabetical List Data Structures File List Data Fields Globals

Linked Lists

Linked list utilities. More...

Files
file	BinaryTrees.c
	Binary trees.
file	DoubleLinkedLists.c
	Double linked lists.
file	LinkedLists.c
	Single and indirect linked lists.
file	LinkedLists.h
	Linked lists header.
Data Structures
struct	BinaryNode
	A node in a binary tree. More...
struct	DoubleNode
	A node in a double linked list. More...
struct	IndirectNode
	A node in a linked list that additionally points to a node in another list. More...
struct	Node
	A node in a single linked list. More...
Defines
#define	NbrNodes(linkedList) FindLast(linkedList, NULL)
	Returns the number of nodes in a list. More...
#define	SortedDoubleToBinary(l) SortedDoubleToBinaryWithSize(l, NbrNodes((NodePtr)(l)));
	Transforms a double linked list into a binary tree. More...
Typedefs
typedef unsigned char	UInt8
typedef signed char	SInt8
typedef unsigned short	UInt16
typedef signed short	SInt16
typedef unsigned long	UInt32
typedef signed long	SInt32
typedef Node	Node
	A node in a single linked list. More...
typedef Node *	NodePtr
	A node in a single linked list. More...
typedef IndirectNode	IndirectNode
	A node in a linked list that additionally points to a node in another list. More...
typedef IndirectNode *	IndirectNodePtr
	A node in a linked list that additionally points to a node in another list. More...
typedef DoubleNode	DoubleNode
	A node in a double linked list. More...
typedef DoubleNode *	DoubleNodePtr
	A node in a double linked list. More...
typedef BinaryNode	BinaryNode
	A node in a binary tree. More...
typedef BinaryNode *	BinaryNodePtr
	A node in a binary tree. More...
Functions
void	InsertInTree (BinaryNodePtr theNode, BinaryNodePtr root, SInt8(CompareFunction)(NodePtr a, NodePtr b))
	Inserts a node in a binary tree. More...
BinaryNodePtr	SortedDoubleToBinaryWithSize (DoubleNodePtr linkedList, UInt32 size)
	Transforms a sorted double linked list into a binary tree. More...
DoubleNodePtr	BinaryToDouble (BinaryNodePtr root, UInt8 fillPrev)
	Transforms a (sorted) binary tree to a sorted double linked list. More...
IndirectNodePtr *	LeftNodeRight (BinaryNodePtr node, IndirectNodePtr *theList)
	Used only for the `BinaryToDouble` function. More...
void	BalanceTree (BinaryNodePtr *root)
	Balances a binary tree. More...
void	InvertDoubleList (DoubleNodePtr *doubleLinkedListPtr)
	Same as InvertList, but for double linked lists, and much faster. More...
UInt32	FindFirst (DoubleNodePtr linkedList, DoubleNodePtr *first)
	Same as FindLast, but backwards with a double linked list. More...
void	FillPrev (DoubleNodePtr linkedList)
	Fills the `"prev"` values. More...
UInt32	DestroyLinkedList (NodePtr linkedList, UInt8(*DestructorFunction)(NodePtr theNode))
	Destroys all elements in a linked list. More...
UInt8	DestroyIndirectNode (NodePtr theNode)
	Destroys an indirect node. More...
UInt32	FindLast (NodePtr linkedList, NodePtr *last)
	Finds the last node in a linked list. More...
NodePtr	GetNthNode (NodePtr linkedList, UInt32 n)
	Finds the Nth node of a linked list. More...
NodePtr	SplitAtNth (NodePtr linkedList, UInt32 n)
	Splits a linked list in two. More...
IndirectNodePtr	FindAndList (NodePtr linkedList, UInt8(*IsWhatIWant)(NodePtr theNode))
	Finds nodes in a linked list based on a "matching" function. More...
NodePtr	FindAndMoveOut (NodePtr linkedListPtr, UInt8(IsWhatIWant)(NodePtr theNode))
	Finds and removes nodes based on a "matching" function. More...
void	ApplyIndirectOnSimple (IndirectNodePtr indirectList)
	Applies an indirect linked list on a linked list. More...
void	InvertList (NodePtr *linkedListPtr)
	Inverses a linked list. More...
void	SplitAndMergeSort (NodePtr linkedList, SInt8(CompareFunction)(NodePtr a, NodePtr b))
	Sorts a linked list. More...

Detailed Description

Linked list utilities.

Those are Link List utility functions. They help the maintenance and use of single linked lists, double linked lists and of binary trees. They are very low-level, thus making use of it will require use of typecasting. The trick is to make a new structure that starts with the exact same contents as the Node structure. Here's an example:

  struct MyNode {
    Node n;
    int val;
  };

Define Documentation

#define NbrNodes ( linkedList ) FindLast(linkedList, NULL)

Returns the number of nodes in a list.
This is actually a macro, so be careful.
Definition at line 87 of file LinkedLists.h.
Referenced by InvertList(), and SplitAndMergeSort().

#define SortedDoubleToBinary ( l ) SortedDoubleToBinaryWithSize(l, NbrNodes((NodePtr)(l)));

Transforms a double linked list into a binary tree.
This is a shortcut to the function SortedDoubleToBinaryWithSize.
See also:
SortedDoubleToBinaryWithSize()

Definition at line 108 of file LinkedLists.h.
Referenced by BalanceTree().

Typedef Documentation

typedef struct BinaryNode BinaryNode

A node in a binary tree.
This node points to the left and right child in a binary tree.

typedef struct BinaryNode * BinaryNodePtr

A node in a binary tree.
This node points to the left and right child in a binary tree.

typedef struct DoubleNode DoubleNode

A node in a double linked list.
This node points to both directions in a linked list. Because it starts with the next pointer, it can be safely typecasted as a Node.

typedef struct DoubleNode * DoubleNodePtr

A node in a double linked list.
This node points to both directions in a linked list. Because it starts with the next pointer, it can be safely typecasted as a Node.

typedef struct IndirectNode IndirectNode

A node in a linked list that additionally points to a node in another list.
This is made to make an ordered list of some nodes in another, differently ordered list.

typedef struct IndirectNode * IndirectNodePtr

A node in a linked list that additionally points to a node in another list.
This is made to make an ordered list of some nodes in another, differently ordered list.

typedef struct Node Node

A node in a single linked list.
The only thing that is assumed with the use of this function is that any structure that you want to use for a linked list node (whatever is the actual contents) starts with a pointer to the next node.

typedef struct Node * NodePtr

A node in a single linked list.
The only thing that is assumed with the use of this function is that any structure that you want to use for a linked list node (whatever is the actual contents) starts with a pointer to the next node.

typedef signed short SInt16

Definition at line 36 of file LinkedLists.h.

typedef signed long SInt32

Definition at line 38 of file LinkedLists.h.

typedef signed char SInt8

Definition at line 34 of file LinkedLists.h.
Referenced by LeftNodeRight().

typedef unsigned short UInt16

Definition at line 35 of file LinkedLists.h.

typedef unsigned long UInt32

Definition at line 37 of file LinkedLists.h.
Referenced by LeftNodeRight(), and SplitAtNth().

typedef unsigned char UInt8

Definition at line 33 of file LinkedLists.h.
Referenced by FindAndList(), and SplitAtNth().

Function Documentation

void ApplyIndirectOnSimple ( IndirectNodePtr indirectList )

Applies an indirect linked list on a linked list.
Applies the ordering of an indirect linked list on the single list. This means that if an indirect node IndB, that points to node B, is after the indirect node IndA, that points to node A, in the indirect linked list, then this function will make node B be after node A in the single linked list.
Definition at line 182 of file LinkedLists.c.
References Node::next, IndirectNode::nodeHeader, and IndirectNode::nodePtr.

void BalanceTree ( BinaryNodePtr * root )

Balances a binary tree.

Note:
Can be quite slow. You've been warned.

Definition at line 110 of file BinaryTrees.c.
References BinaryToDouble(), and SortedDoubleToBinary.

DoubleNodePtr BinaryToDouble ( BinaryNodePtr root,

UInt8 fillPrev

)

Transforms a (sorted) binary tree to a sorted double linked list.

Definition at line 75 of file BinaryTrees.c.
References ApplyIndirectOnSimple(), DestroyLinkedList(), FillPrev(), LeftNodeRight(), and IndirectNode::nodePtr.

UInt8 DestroyIndirectNode ( NodePtr theNode )

Destroys an indirect node.

Definition at line 43 of file LinkedLists.c.
Referenced by FindAndMoveOut().

UInt32 DestroyLinkedList ( NodePtr linkedList,

UInt8(* DestructorFunction)(NodePtr theNode)

)

Destroys all elements in a linked list.
Destroys all elements in a linked list pointed by "linkedList". The destructor function must destroy the node and return 0 only if no error occured. Returns the number of nodes successfully destroyed.
Definition at line 24 of file LinkedLists.c.
References Node::next.

void FillPrev ( DoubleNodePtr linkedList )

Fills the "prev" values.

Definition at line 56 of file DoubleLinkedLists.c.
References DoubleNode::next, and DoubleNode::prev.

IndirectNodePtr FindAndList ( NodePtr linkedList,

UInt8(* IsWhatIWant)(NodePtr theNode)

)

Finds nodes in a linked list based on a "matching" function.
Using the key function "IsWhatIWant", makes a new indirect list (made of indirect nodes) that lists pointers to found nodes. They are listed in the order that they were found. Call "DestroyLinkedList((Node*)(returnedIndirectList), DestroyIndirectNode);" to destroy the indirect linked list returned by this function.
See also:
DestroyLinkedList()

Definition at line 111 of file LinkedLists.c.
References Node::next, IndirectNode::nodeHeader, and IndirectNode::nodePtr.

NodePtr FindAndMoveOut ( NodePtr * linkedListPtr,

UInt8(* IsWhatIWant)(NodePtr theNode)

)

Finds and removes nodes based on a "matching" function.
Does the same thing as "FindAndList", but also removes all found nodes and places them in a new single linked list, which is the returned value.
See also:
FindAndList()

Definition at line 145 of file LinkedLists.c.
References ApplyIndirectOnSimple(), DestroyIndirectNode(), DestroyLinkedList(), FindAndList(), Node::next, IndirectNode::nodeHeader, and IndirectNode::nodePtr.

UInt32 FindFirst ( DoubleNodePtr linkedList,

DoubleNodePtr * first

)

Same as FindLast, but backwards with a double linked list.

Definition at line 40 of file DoubleLinkedLists.c.
References DoubleNode::prev.

UInt32 FindLast ( NodePtr linkedList,

NodePtr * last

)

Finds the last node in a linked list.
Sets "*last" to point at the last node of the linked lisk pointed by "linkedList", unless "last" is NULL. Returns the numbers of nodes in the list. You can also use the macro function "NbrNodes(NodePtr linkedList);".
See also:
NbrNodes()

Definition at line 57 of file LinkedLists.c.
References Node::next.

NodePtr GetNthNode ( NodePtr linkedList,

UInt32 n

)

Finds the Nth node of a linked list.
Returns a pointer to the Nth node of the linked list, the first node being node 0 (the 0th node), as with arrays.
Definition at line 74 of file LinkedLists.c.
References Node::next.

void InsertInTree ( BinaryNodePtr theNode,

BinaryNodePtr * root,

SInt8(* CompareFunction)(NodePtr a, NodePtr b)

)

Inserts a node in a binary tree.

Definition at line 17 of file BinaryTrees.c.

void InvertDoubleList ( DoubleNodePtr * doubleLinkedListPtr )

Same as InvertList, but for double linked lists, and much faster.

See also:
InvertList()

Definition at line 21 of file DoubleLinkedLists.c.
References DoubleNode::next, and DoubleNode::prev.

void InvertList ( NodePtr * linkedListPtr )

Inverses a linked list.
Inverts the list pointed by *linkedListPtr. So, a->b->c becomes c->b->a. If you plan to do this often, use InvertDoubleList with a double linked list, as it's much faster.
See also:
InvertDoubleList

Definition at line 203 of file LinkedLists.c.
References GetNthNode(), NbrNodes, and Node::next.

IndirectNodePtr* LeftNodeRight ( BinaryNodePtr node,

IndirectNodePtr * theList

)

Used only for the BinaryToDouble function.

See also:
BinaryToDouble()

Definition at line 92 of file BinaryTrees.c.
References BinaryNode::left, LeftNodeRight(), Node::next, IndirectNode::nodeHeader, and IndirectNode::nodePtr.

BinaryNodePtr SortedDoubleToBinaryWithSize ( DoubleNodePtr linkedList,

UInt32 size

)

Transforms a sorted double linked list into a binary tree.

Note:
Ignores the "prev" pointers. So, if you want to pass the result of BinaryToDouble to this function, you don't need to call FillPrev first.

Definition at line 45 of file BinaryTrees.c.
References DoubleNode::next, DoubleNode::prev, and SortedDoubleToBinaryWithSize().

void SplitAndMergeSort ( NodePtr * linkedList,

SInt8(* CompareFuntion)(NodePtr a, NodePtr b)

)

Sorts a linked list.
Given a pointer to the beginning of a linked list and a compare function, this function sorts the list using the "split-merge" algorythm. CompareFunction(NodePtr a, NodePtr b) should return a value < 1 if and only if a is smaller than b.
Definition at line 228 of file LinkedLists.c.
References NbrNodes, Node::next, SplitAndMergeSort(), and SplitAtNth().

NodePtr SplitAtNth ( NodePtr linkedList,

UInt32 n

)

Splits a linked list in two.
Splits the linked list pointed by "linkedList" into 2 linked lists after node "n", the first node being node 0, as with arrays. Returns a pointer to the beginning of the second linked list.
Definition at line 88 of file LinkedLists.c.
References Node::next.

Generated on Sun Dec 23 15:21:00 2001 for ANet by

Linked Lists

Files

Data Structures

Defines

Typedefs

Functions

Detailed Description

Define Documentation

Typedef Documentation

Function Documentation