C Programming

print means print, f means formatting

or

printf is a output statement function in the C run-time library

example:

printf ("the value of A is %d\n", A);

Compiler - Translates High level language (C, C++ etc.) and generates Object code (machine readable but not directly executable)

Interpreter - Same as compiler but do that interactively (simply saying line by line). Interpreted languages don't usually require a linker, and employ a loading process different from that of a compiled program: the interpreter itself is linked and loaded like a compiled program (and in all probability is a compiled program), but the program interpreted by the interpreter is typically loaded through interpreter-specific means.

Linker - Connects the compiler generated object code with library code to generated independent executable (like in C, you dont write how printf() works, linker add the code for printf() function in your program)

Loader - Load the machine readable codes in memory to be executed. This step typically includes relocating the code output by the linker to a specific memory location into which the program was being loaded.

In a linked list, there is no way to find the "min element" or any other element with a specific property except by walking through the entire list. Of course, you could store a pointer to the min element and update that each time the list changes (add ing or deleting an element), which makes the list less generic and a tiny bit slower but is worth it if you need this min element often.

Pseudocode for finding the min element (I'm assuming you're storing values and you want the element with the lowest value):

ptr_minelement = null;
ptr_element = ptr_firstelement;
while (ptr_element != null) {
if (ptr_minelement == null) or (ptr_minelement->value > ptr_element->value)
ptr_minelement = ptr_element;
ptr_element = ptr_element->ptr_next;

}

Object oriented computer programming and design methodology has become popular as a way of modeling and solving many programming problems. Traditionally, the implementation of such systems has been performed using an object oriented programming language such as C++. Those skilled in the art know that object oriented programming languages share at least five unique and defining concepts or notions. These concepts, which are discussed fully in the relevant literature pertaining to object oriented programming, are known as: CLASSES, OBJECTS; INHERITANCE; POLYMORPHISM, and ENCAPSULATION. Objects communicate with one another via "message passing." A "message" is texts string such as "redraw you". When an object receives a message, a corresponding class method is executed. It is well-known that in object oriented programming, different objects of an object oriented programming language will respond to messages differently.

Shift from top-down to OOP could be called going from fourth to fifth generation, in that what it enables programmers to do better or more conveniently than they could with the more primitive languages resembles what the higher generation languages enabled them to do over the lower generation ones. OOP, however, is a paradigm shift as significant as that from first to second or, arguably, from second to third -- but far more radical than the from third to fourth. Of course, it is impossible to quantify this, but in terms of ease of programming and what OOP enables, it might be fair to say the leap from fourth-generation languages to OOP, especially what OOP has now become, can be likened to the span between binary code and BASIC. OOP supercharges the program environment.

At each generational jump from binary to assembly language, to third-generation, to fourth-generation, the leap made programming easier and enabled more complex tasks by adding layers around the central core of binary code and its next outer layer, assembly. All programming languages including the advanced OOP iterations that are out now, are parsed down to binary to be executed by the computer. It's all fundamentally the same.

OOP packaged the laborious and error-prone systems of calling subroutines with variable parameters we used in the old days with a very slick interface, an envelope of error-checking and ease of use.

Object Oriented Programming organizes programming logic around objects instead of processes (as is the case with non-OOP). Some widely used third generation, object-oriented programming languages include C++, Java, and Smalltalk. In OOP, data, and the processes that can be performed on the data, are combined into an object. In addition, objects with similar characteristics may be combined into something called a class. So when an OOP programmer creates a class and wants to categorize certain files they are able to create a sub-class. Sub-classes inherit all the characteristics and processes from the original class file that it is derived from. Inheritance is one of the most powerful features of OOP. Once a programmer creates the subclass, he can add to or change the characteristics and processes to meet the precise needs of the subclass. An example of an OOP is Microsoft Office Suite products (Word, Excel, PowerPoint, Access). First Generation Programming is a machine language. It only understands zeros and ones, so we say machine languages are binary. Second Generation Programming is also called assembly languages; it uses simple words in place of zeroes and ones. The programmer associates each assembly language statement with a specific machine language command. Third Generation Programming uses source codes that could then convert into machine language. A special computer program, called a compiler, would handle the conversion. A compiler is a computer program that translates a specific third generation language (3GL) into machine language. Forth Generation Programming languages are closer to natural language. People who have little or no programming skills can use them to write simple programs. One example of a 4GL is structured query language (SQL). Structured query language is a standard language for manipulating databases. Users can write simple SQL programs to create a database, enter data, retrieve data, and delete data. How are they similar? All programming languages still go back to the First Generation Programming language, Each generation has become more advance, with better tools and features. But each language resorts to machine language.

Linked lists are dynamic linear data containers.

They are linear because each item has one adjacent item in each direction (there is a predecessor, or none, and a successor, or none, to each item, but never more than one in each direction).

They are dynamic because the size is not generally fixed and potentially infinite. To manage such a dynamic structure, memory for new items is allocated at runtime, and the different items are connected, or linked, through pointers.

In a single linked list, a single pointer points from one item to the next item.

In a double linked list, one pointer points from one item to the next item, and a second pointer points to the previous item in the list.

The purpose of a pointer is to store a memory address and to allow indirect access to the value stored in that memory address. The act of indirectly accessing memory through a pointer is known as dereferencing. Thus a pointer is said to hold a reference; it "points" to the reference. However, a reference and a pointer are not the same thing. A reference is an alias, an alternate name by which we can refer to an existing object. An object can have many aliases, but aliases does not require any memory over and above that of the object itself, unlike a pointer which does require memory.

The address of a reference is always the address of the object being referred to (just as Bill and Billy are different ways of referencing someone with the name William). However the address of a pointer is always the address of the pointer itself; it is a variable just like any other. The value of a pointer is the address that is stored in the pointer; the address of the object being referenced by the pointer. The dereferenced value of the pointer is the value stored at that memory address; the value of the referenced object itself.

In C++, we can enumerate all the properties of a variable, a reference to that variable and a pointer to that variable like so:

int i = 42; // instantiate an integer with the value 42

std::cout<<"Address of integer: 0x"<<&i<

std::cout<<"Value of integer: "<

int& r = i; // refer to i

std::cout<<"Address of reference: 0x"<<&r<

std::cout<<"Value of reference: "<

int* p = &i; // point to i

std::cout<<"Address of pointer: 0x"<<&p<

std::cout<<"Value of pointer: 0x"<

std::cout<<"Dereferenced value of pointer: "<<*p<

The output of this code would be something like this:

Address of integer: 0x00FBFBAC

Value of integer: 42

Address of reference: 0x00FBFBAC

Value of reference: 42

Address of pointer: 0x00FBFB94

Value of pointer: 0x00FBFBAC

Dereferenced value of pointer: 42

The actual memory addresses may be different on your system. However, note that the address of the reference is the same as the address of the integer, the object being referenced. Thus r and i are aliases, different names that refer to the same object. As such they have the same value. After all, the are one and the same object. The address of the pointer, however, is a different address. This proves that pointers are variables like any other; they have an address all of their own. Note also that the value of the pointer is the address of i (and, by extension, the address of r). The third property, the dereferenced value, is unique to pointer types. This returns the value of the object that is referenced by the pointer value.

This is obviously a trivial example and doesn't cover the full range of a pointer's potential, however it's important to understand the difference between a pointer and a reference. Not all languages that support pointers also support references like C++ does, thus you will often see the terms pointer and reference being used interchangeably. C is a typical example because it has no concept of a dedicated reference types but it does have pointer types. To be crystal clear, a reference is the value stored in a pointer (the address being referred to), it is not the pointer itself.

Aside from the semantic difference, another difference between a pointer and a reference is that a reference must always refer to something whereas a pointer need not. When a pointer doesn't refer to anything in particular, it is assigned address zero. Memory address zero is a reserved address which cannot be dereferenced and a pointer that holds the value zero is said to be a null pointer. The importance of the null pointer will become clear.

Now that we have an understanding of what pointers can actually do, what are the advantages and disadvantages?

The main advantage is that we can use pointers to pass objects into functions by reference. Languages like C and C++ use pass by value semantics by default which means that when we pass an object to a function, the object is copied; only the value of the object is passed, not the object itself. If we want the function to operate upon the object itself, we must pass the object by reference, not by value. C has no concept of a reference, let alone pass by reference, but if we pass a pointer to the object, the pointer is passed by value, and since the value is a memory address, it is the same as passing the object itself, by reference.

This is both an advantage and a disadvantage. It is advantageous in that we can pass objects by reference, but it is disadvantageous because we must be certain the pointer is non-null before we can actually operate upon it. This means that every function that accepts a pointer as an argument will have to perform the exact same test upon that pointer; does the pointer actually point at something valid? In C++ we don't have this problem because we can simply uses a reference instead of a pointer argument. References can never be null; they must always refer to a valid object thus there's no need to test the reference.

However, sometimes we want to pass an object as an optional parameter rather than a required parameter, so passing a null pointer would be acceptable. We still have to perform the test for non-null, but there's no way to pass an object as an optional parameter other than by instantiating a default object which can be considerably less efficient than simply testing if a pointer is zero or not.

Another advantage of a pointer is that when we wish to allocate memory dynamically, we must keep track of the start address of the allocation. The operating system's memory manager knows exactly how much memory is allocated to each address, so when we're finished with a block of memory, all we really need is the start address and the memory manager takes care of the rest, making that block of memory available to any thread or process that requires it. However, sometimes the memory manager may report that there is insufficient memory to meet an allocation, so no memory can be allocated. That's not a problem because if an allocation cannot be met, the operating system returns address zero as the start address. so each time we make an allocation, we simply store the value returned by the allocator in a pointer. If it is null, there is no memory available. We cannot use references for this purpose because references cannot be null, thus a pointer is clearly advantageous here.

In languages that do not support pointers, such as Java, memory is allocated to the Java virtual machine (using internal pointers of course) and the JVM provides the memory management required by its programs. There's still the chance of running out of memory, but the onus of responsibility shifts to the JVM's memory manager, away from the programmer, which leads us to one of the biggest disadvantages of pointers.

If the programmer fails to keep track of memory allocations, the program will inevitably leak memory (known as a resource leak). That is, if he allows all pointers to a memory resource to fall from scope, there's no way to recover the start address and thus no way to release the memory to the system. The problem with pointers is that there is no concept of resource ownership. A pointer simply holds a memory address, but there's no way to determine if that pointer actually owns the memory it is pointing at or if it simply referring to memory that is shared. In truth, all memory is shared and no pointer can physically own the memory it points at. We can easily end up with hundreds of pointers to the same object. Therefore the programmer needs to take extra care to ensure that whenever memory is released back to the system, all pointers to that memory must be immediately nullified. This is easier said than done, because not all pointers may be in scope at the point the memory is released, thus they will still be pointing at what they believe is valid memory. Any attempt to dereference memory that has already been released will result in undefined behaviour because that memory may have already been reallocated so it may not even belong to our program let alone still be in a valid state. And if we attempt to release the same memory twice, undefined behaviour is the least of our worries. So it's important that the programmer be aware of memory ownership, even though there's no way to actually define that ownership with a pointer.

In C++ this is less of a problem because we can encapsulate resources in special classes known as resource handles. Technically, a resource handle is a smart pointer. It behaves exactly like an ordinary pointer would, except that when the smart pointer falls from scope it automatically releases its resource. Thus ownership of the resource falls to the resource handle itself. A resource handle can also pass ownership to another resource, thus ownership of a resource becomes more explicit. If we wish to share ownership, we can use specialised resources handles that deal with shared resources through reference counting. The count is increment each time we add a new handle to a resource and decremented each time we release a handle to that resource. When the count reaches zero, the resource is released when the one and only remaining handle falls from scope. We can also use weak references to shared memory. Weak references are more like ordinary pointers except they cannot release resources, but when a shared resource falls from scope, the weak references are automatically nullified. In languages that do not support resource handles, the onus is entirely upon the programmer to manage their own resources through "raw" pointers, which is a distinct disadvantage and is often less efficient because of the complexity of defining resource ownership in a system where ownership is not a native concept.

When used properly and in an organised manner, pointers have many advantages and can lead to more efficient code. For instance, being able to navigate your way through consecutive memory addresses is more efficient than navigating your way through a series of named variables. This is precisely how arrays work, even in languages that do not support native pointers. An array is simply a contiguous block of allocated memory divided into one or more elements of equal size. Knowing the start address of the allocation and the size of each element, we can refer to any one element in the array as an offset address from the start of the array. Of course most languages will provide a more convenient array index operator (technically a suffix operator) that allows use to access individual elements using a zero-based index value ([0], [1], [2], [3], etc). However, behind the scenes, we're actually doing pointer arithmetic. The 3rd element in an array can be found at index [2], but what this really means is that the element resides at the 2nd offset from the start of the array. Thus if an element is 4 bytes in length, the 3rd element will be found at the address that is 2 * 4 bytes from the start of the array. Simple pointer arithmetic like this is a constant time operation, thus we gain constant time random access to any element in the array, whether it is the first element, the last element, or any element in between.

Arrays are by far the most compact and efficient method of storing data elements of the same length and type. However arrays are not ideally suited to data that is variable length. This is because every time we add a new element to an array we must reallocate the array, which may mean copying the array to new memory. There are ways to minimise the need for reallocations, such as allocating more memory than is actually required, however this undermines the efficiency by allocating memory that might not be needed. Moreover, removing elements is problematic because we can only efficiently remove the last element in an array. In order to keep track of unused elements, the unused elements must reside at the end of the array so we only need to maintain a count of those elements, not where each one is. If we remove any other element besides the last, we must move all the elements that follow it in order to close the gap and move the gap into the unused block.

To maintain efficiency we can use other structures that do not require contiguous memory. For instance, rather than allocating a single contiguous block of memory we can divide the memory into separate blocks of equal size. Thus when we run out of space, we simply allocate a new block, leaving the original blocks in place; no need to reallocate them. This is achieved by creating an array of pointers, where each pointer refers to a separate block. We use additional memory to maintain this array, but we now have the advantage that an array can grow and shrink more efficiently without having to reallocate the existing blocks. In effect, we're actually creating an array of arrays, otherwise known as a multi-dimensional array. However, since the controlling array contains pointers and the value of a pointer is a memory address, we still have constant-time random access to any element, because when we refer to a pointer by its index within the pointer array, the return value is another array, thus we can use a two-dimensional suffix to access an individual element, just as if we'd allocated the array as a single contiguous block. This would not be possible without pointers.

Moreover, we can also more easily remove and insert elements from either end of the array, but not from the middle.

If we need to add or remove lots of elements in the middle of a structure, then we need a more complex structure known as a linked list. Each element in a linked list is a node and each node points to the next node. The last node, the tail node, simply points to null and we only need to keep track of the first node, known as the head node. We lose constant time random access as well as bidirectional access because, to locate any node, we must traverse the pointers from the head node. However, since the structure is now encapsulated by the nodes themselves, the nodes can physically reside anywhere in memory and we can insert and extract nodes simply by adjusting the internal pointers between the affected nodes. For instance, if we have nodes x, y and z where x points to y and y points to z, in order to remove y we first navigate our way from the head until we reach x (because it points to y, the node we wish to delete). We then copy the value of y's pointer (which holds the address of z). We can then release y from memory and finally replace x's pointer with the value we copied. So x now points to z.

With a linked list, all insertions must be done at the head because that's the only node we have constant time access to. However, if we point the tail back at the head instead of null we create a circular linked list. Since the tail now points at the head, if we keep track of the tail rather than the head then we get constant time access to both the head and the tail. Now we can insert at either end of the list in constant time. Although lists do not allow constant time access to any element in the lists, if we need to perform a lot of insertions in the middle of the list, it is more efficient than using an array because we only need to maintain the internal links of the affected nodes, we don't have to reallocate or move elements around in order to make room for insertions or cater for extractions. The pointers consume additional memory of course (one word per element) however it is more efficient overall. If we require bidirectional traversal, then we can add a second pointer to each node so that they point to the previous element as well as the next.

The concept of a bidirectional node can be extended so that rather than simply pointing forwards and backwards through a list, we can point left and right to construct binary trees, where every node has up to 2 child nodes. These are particularly useful when we wish to sort data. Each node represents the root of its own subtree such that the left node points to a subtree with values that are less than this node's value while the right node points to a subtree with values that are not less than this node's value. Thus when we insert values, we simply navigate from the root of the tree, traversing left or right according to the value in the current node until we reach a null pointer in the required direction. We then insert a new node at that position. If there is no root, the value simply becomes the root node. New nodes always have null child pointers.

Of course a binary tree can easily end up unbalanced such that there are more nodes on one side of the root than the other. To improve efficiency, we can adjust the internal pointers upon each insertion to maintain balance, making it more efficient to locate a value regardless of which side of the subtree it is situated. To enable this balancing, we need to insert sentinel nodes, which uses additional memory, but improves the overall efficiency of the structure. These trees are typically known as self-balancing trees or red/black trees.

All these non-contiguous structures (and more besides) share a common aspect in that they all use pointers to iterate through the sequence. In C++ we can take advantage of this and create an iterator class. This behaves much like a pointer would (and is not unlike a smart pointer in that respect), but we can overload the increment and decrement operators to make traversal of these structures more intuitive. Normally, when we increment a pointer, the value of a pointer is incremented or decremented by the number of bytes dictated by its type. But an iterator can be forced to replace its value with that of another pointer. Thus if we have an iterator to the start of a sequence and we increment that iterator, we automatically traverse to the next element in the sequence.

Pointers clearly have many advantages, but not all languages implement them. This is primarily because pointers are low-level and require a lot of knowledge and skill to use them properly and safely. High-level languages do implement pointers but they hide the low-level implementation details within objects including resource handles, smart pointers, iterators and so on. Thus complex structures like lists and binary trees are still possible in high level languages without using raw pointers but, behind the scenes, there's still a lot of raw pointer arithmetic going on, it's simply hidden from view and that much harder to reach them (if at all). But knowing what's going on behind the scenes inevitably leads to more efficient code and who knows...? It may even spark an interest in getting to grips with low-level coding. If you want speed and efficiency, pointers are the fundamental means of achieving it.

In order to swap two values in computer memory you need to temporarily store one of those values during the exchange. That is, to swap the values of object's A and B we must perform the following steps where T is a temporary object:

1. Copy the value of A to T
2. Copy the value of B to A
3. Copy the value of T to B

Note that this algorithm does not implement a "perfect swap". That is, when two people (the objects) swap their house keys (the values), we don't require a third person (the temporary object) to hold a copy of one of those keys, we simply hand the actual keys over (perhaps even simultaneously). No copies are made or indeed required -- we simply "move" values from one place to another.

But a computer cannot move values from one place to another, it has to copy them via assignment. If we assign the value of B to A then both A and B would hold the same value. The original value of A is lost, hence we require a temporary object to hold the value of A.

Note that although languages like C++ support a native move operation, the move operation applies to resource handles only. When we swap a resource, the resources don't actually move, the only thing that changes is the "owner" of the resource. That is, it is the handle's that swap, not the resources. Even so, with move semantics we still need a temporary:

1. Move ownership of A's resource to T
2. Move ownership of B's resource to A
3. Move ownership of T's resource to B

This is as close to the "perfect swap" as we can get, but it does not apply to primitive data types like numbers because the notion of "ownership" only applies to resource handles. The most efficient way to "move" a primitive data type is simply to copy it.