The greatest mistake you can make in life is to be continually fearing you will make one

Friday 29 January 2010

LIST ADT

LIST:
       A list is a sequential data structure, ie. a collection of items accessible one after another beginning at the head and ending at the tail.
  • It is a widely used data structure for applications which do not need random access
  • Addition and removals can be made at any position in the list 
  • lists are normally in the form of a1,a2,a3.....an. The size of this list is n.The first element of the list is a1,and the last element is an.The position of element ai in a list is i.
  • List of size 0 is called as null list.
 Basic Operations on a List
  • Creating a list
  • Traversing the list
  • Inserting an item in the list
  • Deleting an item from the list
  • Concatenating two lists into one 
  Implementation of List:

    A list can be implemented in two ways
  1. Array list
  2. Linked list
 1.Storing a list in a static data structure(Array List)
  •  This  implementation stores the list in an array.
  • The position of each element is given by an index from 0 to n-1, where n is the number of elements.
  • The element with the index can be accessed in constant time (ie) the time to access does not depend on the size of the list.
  • The time taken to add an element at the end of the list does not depend on the size of the list. But the time taken to add an element at any other point in the list depends on the size of the list because the subsequent elements must be shifted to next index value.So the additions near the start of the list take longer time than the additions near the middle or end.
  • Similarly when an element is removed,subsequent elements must be shifted to the previous index value. So removals near the start of the list take longer time than removals near the middle or end of the list.
Problems with Array implementation of lists:  
  • Insertion and deletion are expensive. For example, inserting at position 0 (a new first element) requires first pushing the entire array down one spot to make room, whereas deleting the first element requires shifting all the elements in the list up one, so the worst case of these operations is O(n).
  • Even if the array is dynamically allocated, an estimate of the maximum size of the list is required. Usually this requires a high over-estimate, which wastes considerable space. This could be a serious limitation,  if there are many lists of unknown size.
  •  Simple arrays are generally not used to implement lists. Because the running time for insertion and deletion is so slow and the list size must be known in advance
2. Storing a list in a dynamic data structure(Linked List)
  • The Linked List is stored as a sequence of linked nodes which are not necessarily adjacent in memory.
  • Each node in a linked list contains data and a reference to the next node 
  • The list can grow and shrink in size during execution of a program.
  • The list can be made just as long as required.It does not waste memory space because successive elements are connected by pointers.  
  • The position of each element is given by an index from 0 to n-1, where n is the number of elements.
  • The time taken to access an element with an index depends on the index because each element of the list must be traversed until the required index is found.
  • The time taken to add an element at any point in the list does not depend on the size of the list,as no shifts are required
  • Additions and deletion near the end of the list take longer than additions near the middle or start of the list. because the list must be traversed until the required index is found
Array versus Linked Lists


1.Arrays are suitable for 
        - Randomly accessing any element.
        - Searching the list for a particular value
        - Inserting or deleting an element at the end.
2.Linked lists are suitable for 
        -Inserting/Deleting an element.
        -Applications where sequential access is required.
        -In situations where the number of elements cannot be predicted beforehand.
  

20 comments:

  1. For most up-to-date information you have to pay a visit world-wide-web and on internet I found this web page as a most
    excellent site for latest updates.
    Also see my website - Teens who love to fuck

    ReplyDelete
  2. This page certainly has all the info I wanted about this subject and didn't know who to ask.
    my site: porn

    ReplyDelete
  3. There is definately a great deal to know about this subject.
    I like all of the points you made.
    Here is my homepage ... cheap fixer upper homes PA

    ReplyDelete
  4. It is not my first time to go to see this web page, i am visiting this web site dailly and
    get nice data from here all the time.
    Look at my site - video chatting free

    ReplyDelete
  5. Hello, just wanted to say, I loved this blog post. It was
    practical. Keep on posting!
    My web page: proform coupon code

    ReplyDelete
  6. Malaysia & Singapore & brunei ideal internet
    blogshop for wholesale & supply korean add-ons, earrings, earstuds,
    pendant, rings, bracelet, trinket & hair accessories.
    Deal 35 % wholesale discount. Ship Worldwide
    Here is my web site ... La Fiesta

    ReplyDelete
  7. What's up, the whole thing is going nicely here and ofcourse every one is sharing data, that's really good, keep up writing.
    Also visit my weblog : click the next internet site

    ReplyDelete
  8. An impressive share! I have just forwarded
    this onto a friend who has been doing a little research on this.
    And he actually ordered me lunch simply because I found it for him.
    .. lol. So let me reword this.... Thank YOU for the meal!
    ! But yeah, thanks for spending some time to discuss this
    subject here on your internet site.
    Feel free to surf my web page :: Pre-owned boats ecommerce specialist

    ReplyDelete
  9. Howdy! I could have sworn I've been to this website before but after reading through some of the post I realized it's new to me.

    Anyhow, I'm definitely glad I found it and I'll be book-marking and checking
    back frequently!
    My webpage :: best seo

    ReplyDelete
  10. Very nice post. I just stumbled upon your blog and wished to say that I have really enjoyed surfing around your blog posts.
    After all I will be subscribing to your feed and I hope you
    write again soon!
    Also visit my web-site :: Casino

    ReplyDelete
  11. Have you ever considered writing an e-book or guest authoring on
    other websites? I have a blog centered on
    the same information you discuss and would really like to have you share some stories/information.
    I know my audience would appreciate your work. If you're even remotely interested, feel free to shoot me an email.
    My web page - outsource philippines

    ReplyDelete
  12. We absolutely love your blog and find most of your post's to be just what I'm looking for.

    Does one offer guest writers to write content to suit
    your needs? I wouldn't mind publishing a post or elaborating on a number of the subjects you write with regards to here. Again, awesome site!
    Also visit my web-site : visit this website

    ReplyDelete
  13. I'm gone to say to my little brother, that he should also go to see this blog on regular basis to obtain updated from newest news update.

    Here is my web page: get the 411 pain

    ReplyDelete
  14. What's up to all, how is all, I think every one is getting more from this site, and your views are nice designed for new users.

    Here is my weblog :: manfrotto

    ReplyDelete
  15. Hi to all, because I am really keen of reading this web site's post to be updated regularly. It includes nice data.

    my homepage ... "quartern"

    ReplyDelete
  16. Thanks for finally talking about > "LIST ADT" < Liked it!

    Also visit my web-site: topsportsmodel

    ReplyDelete
  17. Wonderful, what a blog it is! This weblog presents useful information to us, keep it up.



    My web page; graduate certificate programs online

    ReplyDelete
  18. great issues altogether, you just won a logo new
    reader. What could you suggest about your publish that you simply made a few
    days in the past? Any sure?

    Feel free to visit my web-site :: kitchen cabinet

    ReplyDelete
  19. Hello, its fastidious paragraph regarding media print, we
    all be familiar with media is a enormous source of facts.


    my site ... kitchen cabinet

    ReplyDelete
  20. Its like you read my mind! You seem to know so much about this, like you wrote the book in it or something.
    I think that you can do with some pics to drive the message home a little bit, but other than that,
    this is great blog. A fantastic read. I'll certainly be back.

    Here is my blog post; kitchen cabinet

    ReplyDelete