Like Tree2Likes
  • 1 Post By std10093
  • 1 Post By whiteflags

Linked List Process in C

This is a discussion on Linked List Process in C within the C Programming forums, part of the General Programming Boards category; Hi there, I'm new in C programming and i need help with Linked List. I want to build a linked ...

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    108

    Linked List Process in C

    Hi there,
    I'm new in C programming and i need help with Linked List.

    I want to build a linked list that will print the words i enter alphabetically.

    Can someone give me full steps on how to do it?
    I don't need the code.

    I don't know what to put in my main or if i need my main at all.
    Can someone help please?

    I would really appreciate it

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,678
    Every node will be a struct that will hold a string and a pointer to next node of the list.
    You read one word, you create a node.
    You read the 2nd word and you traverse the list until you find where the node with the second node should be placed.
    Continue until you read all the words.

    That's the approach I would use, assuming that the words come to me in a random order..

    Here is a small .h I use for managing a list of integers. It may give you some boost.
    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

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Quote Originally Posted by YannB View Post
    I want to build a linked list that will print the words i enter alphabetically.
    Linked-lists don't print things.
    Perhaps you mean you want to produce a program containing a linked-list of words to print those words alphabetically. In that case you want a sorting algorithm that is appropriate for a linked-list. Insertion sort and merge sort are good candidates for that.

    You should make a start, doing the bits that you do know how to do, and post that.
    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"

  4. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,678
    I think iMalc's idea is more efficient.

    Create the list by inserting every word at the start of the list. Time complexity : O(n)
    Sort with merge-sort, heap-sort or even quicksort : O(nlogn)
    Print the list : O(n)
    Complexity : O(nlogn)

    With my approach, the complexity may be a little bigger, so I think iMalc's should be followed. After all, it seems more clear and easy to do.
    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

  5. #5
    Registered User
    Join Date
    Jan 2013
    Posts
    108
    Yes sorry for being unclear I wanted to know how to build a linked list basted on char instead of int.
    Then sort every word i enter in alphabetical order

    i just need to know the steps after my structure.
    What needs to be in my main.

    Sorry if i'm not clear again

  6. #6
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,678
    You can check the link I provided in post number two. It has a demonstration main as well.
    You should however use as data member of the struct a string instead of an int.
    Also, remember that in C, we use strcmp to compare strings.

    For the stirng you have to choices.
    1-Use as member of the struct an array of chars with a fixed size.
    2-use a char pointer and allocate dynamically (with malloc) the exact space that every word needs. In this case don't forget to first free the string and then the node, when freeing the list.
    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

  7. #7
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,678
    Oh and remember than in case you need to swap two nodes, in my mind it is easier to swap their contents instead of the pointers.

    For example, you have two nodes, 1 and 2.
    Assume that every struct has two data members, an integer and a pointer to the next node.
    In order to swap them, in my way, just copy number two to the first struct and number one to the second struct. You may use a temp variable to swap, but you can do it without one. But, I recommend you use one.
    YannB likes this.
    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

  8. #8
    Stoned Witch Barney McGrew's Avatar
    Join Date
    Oct 2012
    Location
    astaylea
    Posts
    420
    Probably easier just to insert each element in order as you're building the list. Then if you find it's slow for the inputs you want to handle, try doing the same thing with a binary tree instead. Less work for you, in either case. You could handle collisions by storing an unsigned int that keeps track of how many times a single word occurred.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Quote Originally Posted by std10093 View Post
    Sort with merge-sort, heap-sort or even quicksort : O(nlogn)
    Heap Sort is impractical for a linked-list. It's possible to do, but it's horrid.
    Quick Sort is an option, but not an attractive one. It's not ideal for linked-lists, as it suffers from the possibility of becomming O(n*n), which is generally far more likely with most implementations than it is for array sorting. It's a lot more difficult to pick a good splitter, and most implementations tend to pick the worst possible choice much of the time.
    Merge Sort for a linked-list OTOH is always O(n*logn) and is done in-place with no extra buffer.

    Seldom is it ever worth considering anything other than these three for a linked-list:
    Insertion Sort I(n*n), or
    Merge Sort O(n*logn), or
    Bucket Sort ~ O(n*loglogn) (For large n, the number of balls per bucket should follow a Poisson distribution).

    I should also say that if you go the Insertion route, then you can just insert each item as you go, though it makes very little difference overall.
    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"

  10. #10
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,678
    @Barney, I thought of this too, but will it be efficient?
    I mean with every word you receive, you need to traverse the list to find out where the node should be placed. So, that yields in worst case scenario, O(n˛).
    Well if you are planning to use a non-optimum sorting algorithm, then better do it like this. But, most implementations, provide insert at the end or the start of the list, thus you need to make a new method for inserting at i-th position of the list.

    @iMalc, I think mergesort is the one that we would use. Also, quicksort, for a random input, will take O(nlogn).

    But, wouldn't be easy to put the strings into an array, sort the array and then construct the list? We will increase the space complexity but think of the trade off. Sorting a list can be slow. I will follow this approach and I am going to implement it too! Hopefully I will have some results soon.

    //If you need a place to check sorting algorithms, visit iMalc's homepage
    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

  11. #11
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,667
    Sorting a list can be slow
    Sorting a list with mergesort is O(nlogn) in the worst case, and I don't think comparison sorts can go faster than that.
    iMalc likes this.

  12. #12
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,678
    Of course not! Remember the proof with the tree.

    A sorting algorithm is optimum in terms of time if and only if it has time complexity O(nlogn).
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Declaring linked list inside linked list
    By blueboyz in forum C Programming
    Replies: 33
    Last Post: 04-20-2012, 10:13 AM
  2. Process List
    By david84 in forum Windows Programming
    Replies: 4
    Last Post: 09-06-2010, 02:07 PM
  3. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 05:37 PM
  5. Replies: 6
    Last Post: 03-02-2005, 01:45 AM

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