Linked lists can be thought of from a high level perspective as being a series b of nodes. Each node has at least a single pointer to the next node, and in the last node's case a null pointer representing that there are no more nodes in the linked list.
In DSA our implementations of linked lists always maintain head and tail pointers so that insertion at either the head or tail of the list is a constant time operation.
Following are the important terms to understand the concept of Linked List.
1. Insertion is O(1)
2. Deletion is O(n)
3. Searching is O(n)
Out of the three operations the one that stands out is that of insertion. In DSA we chose to always maintain pointers (or more aptly references) to the node(s) at the head and tail of the linked list and so performing a traditional insertion to either the front or back of the linked list is an O(1) operation. An exception to this rule is performing an insertion before a node that is neither the head nor tail in a singly linked list. When the node we are inserting before is somewhere in the middle of the linked list (known as random insertion) the complexity is O(n). In order to add before the designated node we need to traverse the linked list to ¯nd that node's current predecessor. This traversal yields an O(n) run time.
SINGLE LINKED LIST
DOUBLE LINKED LIST
STACK
The stack is a list-like structure in which elements may be inserted or removed from only one end. While this restriction makes stacks less flexible than lists, it also makes stacks both efficient (for those operations they can do) and easy to implement. Many applications require only the limited form of insert and remove operations that stacks provide. In such cases, it is more efficient to use the simpler stack data structure rather than the generic list.
Despite their restrictions, stacks have many uses. Thus, a special vocabulary for stacks has developed. Accountants used stacks long before the invention of the computer. They called the stack a “LIFO” list, which stands for “Last-In, First- Out.” Note that one implication of the LIFO policy is that stacks remove elements in reverse order of their arrival.
It is traditional to call the accessible element of the stack the top element. Elements are not said to be inserted; instead they are pushed onto the stack. When removed, an element is said to be popped from the stack.
As with lists, there are many variations on stack implementation. The two approaches presented here are array-based and linked stacks, which are analogous to array-based and linked lists, respectively.
Operations on a Stack
The following operations are performed on the stack...
1. Push (To insert an element on to the stack)
2. Pop (To delete an element from the stack)
3. Display (To display elements of the stack)
Stack data structure can be implement in two ways. They are as follows...
1. Using Array
2. Using Linked List
Array Based Stack
The array-based stack implementation is essentially a simplified version of the array-based list. The only important design decision to be made is which end of the array should represent the top of the stack. One choice is to make the top beat position 0 in the array. In terms of list functions, all insert and remove operations would then be on the element in position 0. This implementation is inefficient, because now every push or pop operation will require that all elements currently in the stack be shifted one position in the array, for a cost of _(n) if there are n elements. The other choice is have the top element be at position n−1 when there are n elements in the stack. In other words, as elements are pushed onto the stack, they are appended to the tail of the list. Method pop removes the tail element. In this case, the cost for each push or pop operation is only _(1).
Stack using Linked list
The major problem with the stack implemented using array is, it works only for fixed number of data values. That means the amount of data must be specified at the beginning of the implementation itself. Stack implemented using array is not suitable, when we don't know the size of data which we are going to use. A stack data structure can be implemented by using linked list data structure. The stack implemented using linked list can work for unlimited number of values. That means, stack implemented using linked list works for variable size of data. So, there is no need to fix the size at the beginning of the implementation. The Stack implemented using linked list can organize as many data values as we want. In linked list implementation of a stack, every new element is inserted as 'top' element. That means every newly inserted element is pointed by 'top'. Whenever we want to remove an element from the stack, simply remove the node which is pointed by 'top' by moving 'top' to its next node in the list. The next field of the first element must be always NULL.
Download Full Article from given below link: Download PDF
Algorithm For Single Linked List: Download Now
In DSA our implementations of linked lists always maintain head and tail pointers so that insertion at either the head or tail of the list is a constant time operation.
Following are the important terms to understand the concept of Linked List.
- Link − Each link of a linked list can store a data called an element.
- Next − Each link of a linked list contains a link to the next link called Next.
- Linked List − A Linked List contains the connection link to the first link called First
1. Insertion is O(1)
2. Deletion is O(n)
3. Searching is O(n)
Out of the three operations the one that stands out is that of insertion. In DSA we chose to always maintain pointers (or more aptly references) to the node(s) at the head and tail of the linked list and so performing a traditional insertion to either the front or back of the linked list is an O(1) operation. An exception to this rule is performing an insertion before a node that is neither the head nor tail in a singly linked list. When the node we are inserting before is somewhere in the middle of the linked list (known as random insertion) the complexity is O(n). In order to add before the designated node we need to traverse the linked list to ¯nd that node's current predecessor. This traversal yields an O(n) run time.
SINGLE LINKED LIST
DOUBLE LINKED LIST
STACK
The stack is a list-like structure in which elements may be inserted or removed from only one end. While this restriction makes stacks less flexible than lists, it also makes stacks both efficient (for those operations they can do) and easy to implement. Many applications require only the limited form of insert and remove operations that stacks provide. In such cases, it is more efficient to use the simpler stack data structure rather than the generic list.
Despite their restrictions, stacks have many uses. Thus, a special vocabulary for stacks has developed. Accountants used stacks long before the invention of the computer. They called the stack a “LIFO” list, which stands for “Last-In, First- Out.” Note that one implication of the LIFO policy is that stacks remove elements in reverse order of their arrival.
It is traditional to call the accessible element of the stack the top element. Elements are not said to be inserted; instead they are pushed onto the stack. When removed, an element is said to be popped from the stack.
As with lists, there are many variations on stack implementation. The two approaches presented here are array-based and linked stacks, which are analogous to array-based and linked lists, respectively.
Operations on a Stack
The following operations are performed on the stack...
1. Push (To insert an element on to the stack)
2. Pop (To delete an element from the stack)
3. Display (To display elements of the stack)
Stack data structure can be implement in two ways. They are as follows...
1. Using Array
2. Using Linked List
Array Based Stack
The array-based stack implementation is essentially a simplified version of the array-based list. The only important design decision to be made is which end of the array should represent the top of the stack. One choice is to make the top beat position 0 in the array. In terms of list functions, all insert and remove operations would then be on the element in position 0. This implementation is inefficient, because now every push or pop operation will require that all elements currently in the stack be shifted one position in the array, for a cost of _(n) if there are n elements. The other choice is have the top element be at position n−1 when there are n elements in the stack. In other words, as elements are pushed onto the stack, they are appended to the tail of the list. Method pop removes the tail element. In this case, the cost for each push or pop operation is only _(1).
Stack using Linked list
The major problem with the stack implemented using array is, it works only for fixed number of data values. That means the amount of data must be specified at the beginning of the implementation itself. Stack implemented using array is not suitable, when we don't know the size of data which we are going to use. A stack data structure can be implemented by using linked list data structure. The stack implemented using linked list can work for unlimited number of values. That means, stack implemented using linked list works for variable size of data. So, there is no need to fix the size at the beginning of the implementation. The Stack implemented using linked list can organize as many data values as we want. In linked list implementation of a stack, every new element is inserted as 'top' element. That means every newly inserted element is pointed by 'top'. Whenever we want to remove an element from the stack, simply remove the node which is pointed by 'top' by moving 'top' to its next node in the list. The next field of the first element must be always NULL.
Download Full Article from given below link: Download PDF
Algorithm For Single Linked List: Download Now
Hello, my name is Jack Sparrow. I'm a 50 year old self-employed Pirate from the Caribbean.
No comments:
Post a Comment