29-09-2012, 12:40 PM
LINKED LISTS
LISTS.ppt (Size: 986.5 KB / Downloads: 26)
INTRODUCTION
An array is a data structure where elements are stored in consecutive memory locations.
Memory required for the array is allocated in advance.
Hence, an array is also called as static data structure.
If some data has to be inserted or removed from the array in the middle, some amount of data movement occurs. This consumes computer time and decreases program efficiency.
Dynamic data structure where the memory space can be extended.
Ex : linked – lists.
Linked Lists Limitations
Linked lists are traversed in uni direction
Complex to implement
Sequential access to elements
Leads to memory problems if not taken care about the
pointer manipulations properly.
Insertion of a Node
Insertion of a node into a singly linked list
A node can be inserted into a singly linked list in any of the
following three positions.
i. Insertion of a node at the front.
ii. Insertion at the end.
iii. Insertion at any position.
Doubly linked list
Also called as two-way lists or two-way chains where it is
possible to traverse either from left to right or from right to left.
Each node can have any number of data fields and two link fields
which are used to point to the previous node and next node.
There are two NULL: at the first and last nodes in the list.
Advantages:
Given a node, it is easy to visit its predecessor.
Convenient to traverse lists backwards
Circular linked lists
A Circular Linked List is a special type of Linked List.
It supports traversing from the end of the
list to the beginning by making the last
node point back to the head of the list.
A Rear pointer is often used instead of a Head pointer
LISTS.ppt (Size: 986.5 KB / Downloads: 26)
INTRODUCTION
An array is a data structure where elements are stored in consecutive memory locations.
Memory required for the array is allocated in advance.
Hence, an array is also called as static data structure.
If some data has to be inserted or removed from the array in the middle, some amount of data movement occurs. This consumes computer time and decreases program efficiency.
Dynamic data structure where the memory space can be extended.
Ex : linked – lists.
Linked Lists Limitations
Linked lists are traversed in uni direction
Complex to implement
Sequential access to elements
Leads to memory problems if not taken care about the
pointer manipulations properly.
Insertion of a Node
Insertion of a node into a singly linked list
A node can be inserted into a singly linked list in any of the
following three positions.
i. Insertion of a node at the front.
ii. Insertion at the end.
iii. Insertion at any position.
Doubly linked list
Also called as two-way lists or two-way chains where it is
possible to traverse either from left to right or from right to left.
Each node can have any number of data fields and two link fields
which are used to point to the previous node and next node.
There are two NULL: at the first and last nodes in the list.
Advantages:
Given a node, it is easy to visit its predecessor.
Convenient to traverse lists backwards
Circular linked lists
A Circular Linked List is a special type of Linked List.
It supports traversing from the end of the
list to the beginning by making the last
node point back to the head of the list.
A Rear pointer is often used instead of a Head pointer