Like Tree1Likes
  • 1 Post By iMalc

FIFO queue vs Link List

This is a discussion on FIFO queue vs Link List within the C Programming forums, part of the General Programming Boards category; Hello everyone, What is the most distinct differences between a FIFO queue and and a link list. This my first ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    17

    FIFO queue vs Link List

    Hello everyone,

    What is the most distinct differences between a FIFO queue and and a link list.

    This my first post ever, so thank you in advance for your help.

    -DeeMan

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,425
    Welcome to the forum DeeMan!

    A FIFO and a linked list aren't necessarily different. I think it would be best if you took some time to read a few articles on each data structure, and see what you can glean yourself. Then, if you still don't understand something, ask again. Start with these:
    FIFO - Wikipedia, the free encyclopedia
    Linked list - Wikipedia, the free encyclopedia

  3. #3
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    Welcome DeeMan!

    I believe you know that FIFO stands for First In First Out. Only from this, you can imagine some differences (you have to know how a simply link list looks like).

    So, what do you think that are the differences?
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  4. #4
    Registered User
    Join Date
    Feb 2013
    Posts
    17
    Thanks too you both.

    I just finished reading both Wikipedia articles. The FIFO only allows data to be moved and deleted from the top of the array, and data can only be add to the array from the rear. Whereas the link list allows data to be removed, inserted, and delete from anywhere in the array. Is this a correct interpretation. Thanks again for the pleasant experience.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    One could say that:
    A FIFO Queue is a description of the external properties of a container, whereas a linked-list is a description of the internal implementation details of a container.
    They are talking about different aspects of what could be the same thing.
    Tclausex likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,230
    Quote Originally Posted by DeeMan View Post
    Hello everyone,

    What is the most distinct differences between a FIFO queue and and a link list.
    It's sort of like the difference between a forest and a bunch of trees.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #7
    Registered User
    Join Date
    Feb 2013
    Posts
    17
    Are you then saying that the FIFO is a description of how the queue as a whole works, and the link list is the method in which the internal parts are connected? Therefore meaning that a link list can be a FIFO queue, and a FIFO can be a link list? Moreover, a FIFO queue does not have to be linked and a link list does not have to be a FIFO, but they can be one in the same, but not the same at all. Is this where GOD comes from LOL. Just playing, I think it makes a lot more since. When discussing the the queue, its possible to be talking about different aspects of the same thing.

    Thanks all
    -DeeMan

  8. #8
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,425
    I think you more or less get it. A queue and a FIFO are generally synonymous when it comes to programming. They describe the order you process/access/add/delete elements. A linked list describes how those elements are connected, i.e. how the internal order is maintained. You are correct, a FIFO/queue may be implemented as a linked list. It may also be implemented as an array. You could even implement it, if you wanted, using a database like MySQL/PostgreSQL. You are also correct, a linked list may be the basis for a FIFO/queue, it may also be the basis for a LIFO/stack, or a plain old list that allows random access/insertion/deletion.

  9. #9
    Cat
    Cat is offline
    Registered User
    Join Date
    May 2003
    Posts
    1,571
    Quote Originally Posted by DeeMan View Post
    Are you then saying that the FIFO is a description of how the queue as a whole works, and the link list is the method in which the internal parts are connected? Therefore meaning that a link list can be a FIFO queue, and a FIFO can be a link list? Moreover, a FIFO queue does not have to be linked and a link list does not have to be a FIFO, but they can be one in the same, but not the same at all. Is this where GOD comes from LOL. Just playing, I think it makes a lot more since. When discussing the the queue, its possible to be talking about different aspects of the same thing.
    That's basically correct. Fundamentally, there is a distinction between interface and implementation when talking about code. FIFO describes the interface - it describes how other components of the system may interact with this component. A linked list describes the implementation - it describes how the single component works internally.

    Another way to think about this - the interface describes WHAT the code will do, the implementation describes HOW the code will do it. Of course certain implementations work better or worse for different interfaces, but the two concepts are distinct yet complementary.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Priority queue and FIFO
    By Elysia in forum C++ Programming
    Replies: 12
    Last Post: 02-29-2012, 01:32 PM
  2. Help with FIFO queue
    By Martin_T in forum C Programming
    Replies: 10
    Last Post: 11-08-2009, 09:30 AM
  3. understanding queue FIFO
    By arastoo.s in forum C Programming
    Replies: 6
    Last Post: 08-18-2009, 10:16 AM
  4. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  5. want some help with link list and queue
    By farnush in forum C Programming
    Replies: 2
    Last Post: 02-28-2005, 02:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21