Thread: linked lists, what are they for?

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    13

    linked lists, what are they for?

    i dont get it, i really dont see the use at ALL in linked lists. i have read the chapter 15 on the site on them, and understand it. i just need to know why would you ever use them?

  2. #2

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    How would you read and store all the lines of a text file?

    Lists are useful when you don't know in advance how many "somethings" (eg. lines from a file) you need to cope with.

    Sure you could have
    char *lines[1000000];
    but that wastes a lot of space for small files, and doesn't work at all well for very large files.

    But a linked list of lines neither wastes any memory on small files, and is only limited by the physical memory you have available.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    i dont get it, i really dont see the use at ALL in linked lists.
    If you haven't yet, read a tutorial on using something called a <vector>. It is just like an array, but it is much easier to use than an array: you can add or subtract more items at will, you can insert() items or erase() items, and you can sort() the items, etc. Behind the scenes, <vector>'s are implemented as linked lists.
    Last edited by 7stud; 02-25-2005 at 10:20 AM.

  5. #5
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    linked lists rule when you have many insertions or deletions.
    in a linked list: simply unchain the element you want to remove or link the element you want to insert. its just setting a few pointers.

    vectors: inserting an element: resize the vector, shift all elements past the index where you want to insert to the the end by the size of what you want to insert.
    that means: if you insert at the beginning you need to shift ALL elements...

    linked lists have the problem that they cant be accesses randomly (access at beginning or end: constant time, access anywhere else: linear time)
    the advantage is: if you know youre going to insert an element next to a node you already know (e.g. you stored a pointer to it (e.g. head)) then insertion and deletion works in constant time.
    signature under construction

  6. #6
    Registered User
    Join Date
    Dec 2004
    Posts
    95
    std::vector isn't allowed to be implemented as a linked list - it's required to have contiguous memory.

  7. #7
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    just to get this straight:

    vectors and linked list (and maps and sets) are CONTAINERS.
    by convention all containers must provide methods to insert, delete, and lookup element.

    even though the interface of all containers is the same (and you can do the same stuff with them) the complexity (= how many steps (e.g. instructions, comparisions) are required to get the the desired result) of the same method differs between the implementations of the containers.

    looking up an element in a set can be done in O(log(n)) time (that means if there are n elements in the container, a lookup can be done with "only" log(n) comparissions)
    that is because elements in a set are kept in a sorted order - thus a binary search can be done (note that set and map use red/black trees internally - thus even insertion and deletion can be done in O(log(n)) time)

    looking up in a vector or linked list takes O(n) time (meaning if there are n elements youd have to check n elements) since you need to check every element if its the desired one.

    so the basic idea of having different implementations of containers is to increase performance.

    for more information on the stl:
    http://www.sgi.com/tech/stl/
    signature under construction

  8. #8
    Hardware Engineer
    Join Date
    Sep 2001
    Posts
    1,398

    A specific example...

    If you were writing a video editing program, you could use a linked list. Each video-frame could be an element in a linked-list. You want to insert and delete frames while keeping all of the other frames in order. You don't care as much about the absolute frame-number, as the relative position... Move ahead 10 frames... move back 10 frames, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 05:30 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM