What is a Design Pattern?

The most common purpose of design patterns is to make classes reusable and extensible. Design patterns do this by documenting common solutions to common problems.
Since design problems come up again and again in different contexts, it is profitable to learn to recognize common ones. Once you recognize a common problem, you can recall and reuse its solution.
A design pattern is the combination of the problem and its solution.
Programmers are familiar with the concept of an abstract data type. Object-oriented languages and their associated separation of interface from implementation also make possible abstract algorithms; that is, algorithms that do things without precise specifications of how or even what they are doing.

An abstract data type (ADT) defines a data structure in terms of the operations that can be performed on it rather than in terms of a specific implementation. It separates what the data structure does from how it does it.
For instance, linked lists and growable arrays are simply two different implementations of the same linear list ADT since the operations that can be performed on each are the same. In computer science, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior. An abstract data type is defined indirectly, only by the operations that may be performed on it and by mathematical constraints on the effects of those operations. However, the concrete implementation

1. linked list or
2. growable array

affects the performance characteristics of the ultimate code.

Abstract data types are an object-like means of raising the bar on the size of programs that can be written in a purely procedural language. Past a million lines of code, even Object Oriented Design begins to break down. New techniques are needed that allow truly huge programs to be both built and maintained. This is not to say, of course, that these techniques cannot also be used for more complicated programs such as games, word processors, and spreadsheets. In fact, they have been used for these things for many years, sometimes with great success, sometimes with spectacular failure. If you investigate the successes, you will often notice that developers adopted object-oriented principles like data encapsulation even though the language they were coding in did not explicitly support it.
But it's my contention that procedural programming is not the best approach to take for these problems, that OOP more closely matches the way these programs are designed and used, and thus enhances programmer productivity.

Design patterns take abstraction one step further. A design pattern abstracts something you want to do from the actual

1. data structures,
2. algorithms,
3. code,
4. classes, and
5. objects

that fulfill a function.
It decouples the abstract from the specific.
A design pattern is not a particular class, object, data structure, or algorithm, though all of these elements are used to implement patterns. A design pattern is the abstract structure of a common solution to a common problem. It can be implemented in different languages in different ways, and yet still retain its essential flavor.

When faced with a problem to solve, the basic strategy usually taken by we computer scientists is called divide and conquer. It goes like this:

1. Conceptualize the specific problem as a set of smaller sub-problems.
2. Solve each smaller problem.
3. Combine the results into a solution of the specific problem.

Reducing complex problems down to the level of individual states of a few billion bits is what we do all day.
But "divide and conquer" is not the only possible strategy. We can also take a more generalist approach:

1. Conceptualize the specific problem as a special case of a more general problem.
2. Somehow solve the general problem.
3. Adapt the solution of the general problem to the specific problem.

Design patterns are among the major tools in the toolboxes of those who espouse the generalist approach. If you look at samples from a broad spectrum of software solutions, you will find that though the specifics may vary widely, there is often an underlying structural similarity. Searching a filesystem for a file with a particular attribute is in some sense structurally similar to searching an annotated parse tree for a symbol with a particular type. Design patterns codify general solutions to common problems.
The ultimate example of the generalist approach is of course the design and implementation of programming languages themselves. As problem solving tools go, it is hard to get more general than a programming language like C++. When designing new programming languages (or new versions of old programming languages), we think about common problems that are faced every day by real developers and figure out how to create a language which solves them in a general, aesthetically pleasing, and powerful way that is broadly applicable.