I know what a linked lists are and how to code one, but what exactly are some general applications of them. I have tried searching for an answer but can only find the history on them and how to code one.
linked lists are used when constant-time append/delete operations are more important than constant access times for arbitrary items in the list.

For example, arbitrarily sized queues and stacks could both be more efficiently implemented (speed wise, not memory wise) with linked lists than with arrays.
elfprince13 wrote:
linked lists are used when constant-time append/delete operations are more important than constant access times for arbitrary items in the list.

For example, arbitrarily sized queues and stacks could both be more efficiently implemented (speed wise, not memory wise) with linked lists than with arrays.
True story. I've used singly- and doubly-linked list for a whole host of tasks, including storing the names of variables and symbols in my compiler, kcc; keeping track of scheduled process in a small scheduler I built, and more.
elfprince13 wrote:
linked lists are used when constant-time append/delete operations are more important than constant access times for arbitrary items in the list.

For example, arbitrarily sized queues and stacks could both be more efficiently implemented (speed wise, not memory wise) with linked lists than with arrays.


Well, you wouldn't compare a linked list to an array. You would most likely compare it to another ADT, like a vector. And I agree that a queue is more efficient speed wise, but how is a stack? Pushes and pops are constant time at the back of a vector and the back of a linked list. But even though they're both constant time, I would think that a vector would be >= linked lists in practice. Pushing on a linked list requires creating a new node, adding the data, and setting links. In a vector, there is usually already space allocated.

And really, you can make an efficient queue with a vector if you wrap around from the back to the front when you need to, but that would be kinda messy. The logic is a lot clearer with a linked list.

But anyway, the first paragraph is pretty much right, but I think that 'insert' would be more accurate than 'append.'
You can do some other cool things with linked lists that you can't easily do with arrays or vectors. For example, if you ever need to remove a subset of the nodes (like removing the 5 consecutive nodes in the middle of the list), a linked list can do it in O(1) vs. O(n). You can also sort a linked list without needing temporary storage space - not that that really matters all that much.

But really, the applications of a linked list are pretty minimal nowadays, which is why they aren't used very often.
foamy3 wrote:

Well, you wouldn't compare a linked list to an array. You would most likely compare it to another ADT, like a vector. And I agree that a queue is more efficient speed wise, but how is a stack? Pushes and pops are constant time at the back of a vector and the back of a linked list. But even though they're both constant time, I would think that a vector would be >= linked lists in practice. Pushing on a linked list requires creating a new node, adding the data, and setting links. In a vector, there is usually already space allocated.

Vectors are backed by arrays anyway. Yes, if you have some buffer space at the end of the array (and vectors usually do) than you can have constant time push/pop, but you can't guarantee that for all cases.

foamy3 wrote:
But anyway, the first paragraph is pretty much right, but I think that 'insert' would be more accurate than 'append.'

indexed insert operations are still O(n), which is comparable to an array, but yes, if you already have a node reference then inserting after or before can be constant.

kermmartian wrote:
I've used singly- and doubly-linked list for a whole host of tasks, including storing the names of variables and symbols in my compiler, kcc; keeping track of scheduled process in a small scheduler I built, and more.

kcc == Kerm's c compiler?
elfprince13 wrote:
Vectors are backed by arrays anyway. Yes, if you have some buffer space at the end of the array (and vectors usually do) than you can have constant time push/pop, but you can't guarantee that for all cases.


Doesn't matter. A vector will make far fewer malloc calls than a linked list will for a stack. A half dozen malloc calls by a vector is far superior than hundreds of malloc calls by a linked list.
But back to the original question, I once made a hash table and used linked lists as buckets. It was nice because when using the table, I had no idea how many items would be in the buckets. Since there could be (and were, in one application) hundreds of thousands of buckets, extra allocated space could have really racked up.
Same here, I was using the linked list to track the structure of programs under compilation. I also built a hash table to store the variables and symbols, as I mentioned.
foamy3 wrote:
But back to the original question, I once made a hash table and used linked lists as buckets. It was nice because when using the table, I had no idea how many items would be in the buckets. Since there could be (and were, in one application) hundreds of thousands of buckets, extra allocated space could have really racked up.


FYI, vector allocation tops out at a certain amount (it starts by doubling the current size up until a point). Depending on if you used a double linked list or not, you could have easily wasted more space using a linked list than a vector. 4 or 8 bytes of extra space per node * hundreds of thousands of nodes == lots of extra space used Wink

Not that anyone would actually miss the ~1MB of extra RAM used, just saying.
So I realize I am reviving a dead topic but I am having issues. Normal push to front or back linked lists are easy. But I need to create one that sorts in ascending order as items are added. Easy enough, I created three functions that can do that. But as it stands using these functions is a bit difficult and is producing a segmentation fault. Is anyone able to see where the error may be occurring because I have been staring at the code for almost two hours and still can't find it.

Program Code

Code:

#include <iostream>

using namespace std;

class linkedList
{

   public:
      void insert(int);
      void printList();
      linkedList();
   private:
      bool isEmpty();
      void insertBegining(int);
      void insertEnd(int);
      void insertMiddle(int);
      struct node
      {
         int data;
         node* next;
      };
      node* head;
};

linkedList::linkedList()
{
   head = NULL;
}

void linkedList::insertBegining(int item)
{
   node* temp = new node;
   temp->data = item;
   temp->next = head;
   head = temp;
}

void linkedList::insertEnd(int item)
{
   node* temp = new node;
   node* p = head;
   while(p->next != NULL)
   {
      p = p->next;
   }
   temp->data = item;
   temp->next = NULL;
   p->next = temp;
}

void linkedList::insertMiddle(int item)
{
   node* temp = new node;
   node* trailp = head;
   node* nextp = head->next;

   while(item < trailp->data && item > nextp->data)
   {   
      trailp = trailp->next;
      nextp = nextp->next;
   }

   temp->data = item;
   trailp->next = temp;
   temp->next = nextp;
}
void linkedList::printList()
{
   node* temp = head;
   while(temp != NULL)
   {
      cout << temp->data << endl;
      temp = temp->next;
   }
}

bool linkedList::isEmpty()
{
   if (head == NULL)
      return true;
   return false;
}

void linkedList::insert(int item)
{
   node* trailp;
   node* temp = head;
   if(isEmpty())
      insertBegining(item);
   else if(item <= head->data)
      insertBegining(item);
   else {
      while (item > temp->data)
      {
         trailp = temp;
         temp = temp->next;
         if(temp == NULL)
            insertEnd(item);
         else
            insertMiddle(item);
      }
   }
}

int main(int argc, char** argv)
{

   cout << "Now to test the generic Insert Function: " << endl;
   linkedList genericList;
   genericList.insert(10);
   genericList.insert(15);
   genericList.insert(23);
   genericList.insert(13);
   genericList.printList();
}



And the three insert functions do work, so it has to be somewhere in the insert function. I just can't tell where I am going wrong there.

Edit: So I now no longer segfault and the program works. Now I just have to keep adding a little bit more data to it to be sure that I am positive. I won't lie, I did cross post on a more c++ focused forum and they led me to the answer. I got the usual just use the stl responses, but a couple of people also suggesting using gdb. So I did some googling and gdb helped me pinpoint the error. I kind of wish I knew about it a long time ago.
Well the function is 99.9% fool proof. It provides a runtime error with the magic number, 42. It always gets put in between 10 and 13 no matter the order of insertion.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are UTC - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement