Showing posts with label Linked. Show all posts
Showing posts with label Linked. Show all posts

Saturday, 1 June 2013

Program Doubly Linked List Java

Overall Structure of Doubly-Linked Lists

If you wish to traverse a list both forwards and backwards efficiently, or if you wish, given a list element, to determine the preceding and following elements quickly, then the doubly-linked list comes in handy. A list element contains the data plus pointers to the next and previous list items as shown in the picture below.


Of course we need a pointer to some link in the doubly-linked list to access list elements. It is convenient for doubly-linked lists to use a list header, or head, that has the same structure as any other list item and is actually part of the list data structure. The picture below shows an empty and nonempty doubly-linked list. By following arrows it is easy to go from the list header to the first and last list element, respectively.





Download Program With OUTPUT


Linked Stack Java Program

One disadvantage of using an array to implement a stack is the wasted space---most of the time most of the array is unused. A more elegant and economical implementation of a stack uses a linked list, which is a data structure that links together individual data objects as if they were ``links'' in a ``chain'' of data.
Here is a sketch of a linked-list-based ``stack'' that holds 1, then 5, and then 20 at the bottom:
          ---
top ---> | 1 |
         |---|      ---
         | o-|---> | 5 |
          ---      |---|      ----
                   | o-|---> | 20 |
                    ---      |----|
                             |null|
                              ----
The list consists of three ``cells,'' each of which holds a data object and a ``link'' to another cell. A variable, top, holds the address of the first cell in the list. An empty stack looks like this:
top ---> null
(That is, variable top holds value, null.) Each time an object is pushed, a cell is constructed, the object is inserted into the cell, and the cell is linked to the front of the chain of cells. For example, pushing 20 onto the empty stack gives us
          ----
top ---> | 20 |
  |--- | 
  |null|
          ----
After 5 and then 1 are pushed, we obtain the picture first seen.
Say that we pop an object from the stack; the picture changes to this:
                    ---
          top ---> | 5 |
            |---|      ----
                   | o-|---> | 20 |
                    ---      |----|
                      |null|
                              ----
Download Program With OUTPUT

Linked List Java Program

One disadvantage of using arrays to store data is that arrays are static structures and therefore cannot be easily extended or reduced to fit the data set. Arrays are also expensive to maintain new insertions and deletions. In this chapter we consider another data structure called Linked Lists that addresses some of the limitations of arrays.
A linked list is a linear data structure where each element is a separate object.

Each element (we will call it a node) of a list is comprising of two items - the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.
A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. Any application which has to deal with an unknown number of objects will need to use a linked list.
One disadvantage of a linked list against an array is that it does not allow direct access to the individual elements. If you want to access a particular item then you have to start at the head and follow the references until you get to that item.
Another disadvantage is that a linked list uses more memory compare with an array - we extra 4 bytes (on 32-bit CPU) to store a reference to the next node.

Download Program With OUTPUT