473,703 Members | 3,045 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

linked list sorted insert

*** post for FREE via your newsreader at post.newsfeed.c om ***

it's been a while since i have poseted to this newsgroup, but for a long
time i was not programming at all. but now that i am out of college and
facing the prospect of getting a real job, i need to get back into the
game. anyway, i don't know if some of you know the stanford CS library. i
took the problem set a while back and have recently rediscovered it adn
have been trying to solve the problems (in order). this is my attemot at
#6: sorted linked list insert.

6 — SortedInsert()
Write a SortedInsert() function which given a list that is sorted in
increasing order, and a single node, inserts the node into the correct
sorted position in the list. While Push() allocates a new node to add to
the list, SortedInsert() takes an existing node, and just rearranges
pointers to insert it into the list. There are many possible solutions to
this problem.

void SortedInsert(st ruct node** headRef, struct node* newNode) {
// Your code...

/* My code */

void SortedInsert (struct node **headRef, struct node *newNode) {
struct node *prev, *curr = *headRef;

if (*headRef == NULL || newNode -> data <= (*headRef) -> data) {
newNode -> next = *headRef;
*headRef = newNode;
} else {
while (curr && curr -> data <= newNode -> data) {
prev = curr;
curr = curr -> next;
}

prev -> next = newNode;
newNode -> next = curr;
}
}

comments and advice are welcome.

andrew
-----= Posted via Newsfeed.Com, Uncensored Usenet News =-----
http://www.newsfeed.com - The #1 Newsgroup Service in the World!
-----== 100,000 Groups! - 19 Servers! - Unlimited Download! =-----

Nov 13 '05 #1
3 22071
In article <Xn************ *********@208.3 3.61.211>
Andrew Clark <an*****@syr.ed u> writes:
... this is my attemot at #6: sorted linked list insert.

6 0x97 SortedInsert()
[BTW, the character with code 0x97 -- not a printing character in
either ASCII or ISO Latin 1 -- was probably stuck in by some
deficient software. I expanded it for posting purposes.]
Write a SortedInsert() function which given a list that is sorted in
increasing order, and a single node, inserts the node into the correct
sorted position in the list. ...
Just as a general background note, inserting into such a list gives
O(n^2) time behavior on "random" data. It is pretty close to
optimal on reverse-sorted data and pretty much "pessimal" on sorted
data. As such, it is suitable only in relatively rare circumstances,
such as when taking input items one at a time from a human and
displaying the results immediately.

That out of the way, and noting that the problem requires that you
use the function signature that appears in your solution:
void SortedInsert (struct node **headRef, struct node *newNode) {
struct node *prev, *curr = *headRef;

if (*headRef == NULL || newNode -> data <= (*headRef) -> data) {
Given that you already copied "*headRef" into a local variable, why
not use that wherever possible?

if (curr == NULL || newNode -> data <= curr -> data) {
newNode -> next = *headRef;
newnode -> next = curr;
*headRef = newNode;
(but this has to remain *headRef -- you want to change the lvalue
at *headRef, not a copy of that lvalue's value).
} else {
while (curr && curr -> data <= newNode -> data) {
prev = curr;
curr = curr -> next;
}

prev -> next = newNode;
newNode -> next = curr;
}
}

comments and advice are welcome.


This code works and is reasonably clear. It can, however, be
simplified (more than just the *headRef to curr changes above).

Before I get to that, I will also note that you insert an "equal"
item -- one where newNode->data == curr->data, for some node "curr"
-- after all such equal items (probably the right thing to do).
The problem statement never said what *should* happen in such cases;
the most likely alternative to "insert after equal items" is "fail"
(abort, or return an error indication; the latter would of course
require changing the return type of the function). In some other
languages you could even "throw an exception" -- you can even do
this in C by using the bad kind of goto, spelled longjmp(), but I
consider this a bad idea myself.

One of C's unusual features is the ability to take addresses of
local variables, members of structures, and so on. (Many languages
with pointers forbid this sort of thing -- pointers are created
only with "new"-like keywords, and the only other way to obtain a
pointer is to copy an existing, valid pointer.) We can use
this feature to move various tests.

void SortedInsert(st ruct node **headRef, struct node *newNode) {
struct node **pp, *curr;

The "pointer to pointer" variable pp here is the one we will use
in this way. The first step is to make sure pp is just a copy of
headRef:

pp = headRef;

This guarantees that *pp is the lvalue -- loosely, the variable --
that must change in order to insert something at the front of the
list, whether or not the list is empty.

Next comes the tricky bit:

while ((curr = *pp) != NULL && curr->data <= newNode->data)
pp = &curr->next;

On the very first trip through this loop, *pp is the same as
*headRef, i.e., the value of the variable that heads the list.
We copy this to curr just for convenience (to avoid writing *pp
each time). If this value is NULL, the list is empty and we
must stop, but if it is not NULL, we need to check whether the
new node goes here, or later in the list.

If the new node goes here -- i.e., curr->data > newNode->data --
we stop, with pp == headRef and curr (aka *pp) not NULL. Otherwise,
we set pp to the *address* of curr->next and repeat the loop.

This time through the loop, pp == &((*headRef)->next), so *pp --
which we copy to curr as usual -- is (*headRef)->next. Again,
this can be NULL, or it might be a valid node; if it is a valid
node we must see if the new node goes here, or later. If the
new node goes later, we set pp to &((*headref)->next->next),
and so on down the line.

The crucial bit is that, no matter what, when the loop stops, *pp
is "the pointer that leads to curr" -- either *headRef itself, or
&((*headRef)->a->b->c->...->next) for some chain of "non-head"
nodes a, b, c, ..., however many it takes to get there. Moreover,
*pp is the pointer that *should* point to the new node, because
the new node goes before the node now in "curr", or at the end of
the list, whichever is the case. Note that curr == *pp, too, so
we have that saved.

So, now we just need to do this:

*pp = newNode;
newNode->next = curr;

and the insertion is complete. If curr == NULL, we have put the
node at the end of the list, because now newNode->next == NULL.
If pp == headRef, we have put the new node at the front of the
list. If both of those are true, we have done both at the same
time -- put the new node at the head, and also at the end; the head
and end are the same thing. If, on the other hand, curr != NULL,
then curr is the node that should come after newNode, and we have
made that happen.

So now we can finish off the function with a close brace, but for
compactness, here it is in its entirety:

void SortedInsert(st ruct node **headRef, struct node *newNode) {
struct node **pp, *curr;

pp = headRef;
while ((curr = *pp) != NULL && curr->data <= newNode->data)
pp = &curr->next;
*pp = newNode;
newNode->next = curr;
}

Some might prefer the loop as a "for" loop, or moving the initialization
for "pp" up into the declaration line, but the essence of the
algorithm is the same.
--
In-Real-Life: Chris Torek, Wind River Systems (BSD engineering)
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://67.40.109.61/torek/index.html (for the moment)
Reading email is like searching for food in the garbage, thanks to spammers.
Nov 13 '05 #2
Chris Torek wrote:
void SortedInsert(st ruct node **headRef, struct node *newNode) {
struct node **pp, *curr;

pp = headRef;
while ((curr = *pp) != NULL && curr->data <= newNode->data)
pp = &curr->next;
*pp = newNode;
newNode->next = curr;
}

Some might prefer the loop as a "for" loop,
or moving the initialization
for "pp" up into the declaration line, but the essence of the
algorithm is the same.


I like it the way that you have it there.
If it was in a for loop, then one of the optional parts
would be missing, which I think looks funny.
I like to declare and initialize seperately.

--
pete
Nov 13 '05 #3
pete <pf*****@mindsp ring.com> wrote:
Chris Torek wrote:
void SortedInsert(st ruct node **headRef, struct node *newNode) {
struct node **pp, *curr;

pp = headRef;
while ((curr = *pp) != NULL && curr->data <= newNode->data)
pp = &curr->next;
*pp = newNode;
newNode->next = curr;
}

Some might prefer the loop as a "for" loop,
or moving the initialization
for "pp" up into the declaration line, but the essence of the
algorithm is the same.


I like it the way that you have it there.
If it was in a for loop, then one of the optional parts
would be missing, which I think looks funny.
I like to declare and initialize seperately.


Which part would that be?

for (pp = headRef; (curr = *pp) != NULL && curr->data <= newNode->data;
pp = &curr->next)
;
(But I agree -- i prefer the while() version too.)

Stig
--
brautaset.org
Nov 13 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
2069
by: Peter Schmitz | last post by:
Hi, in my application, I defined a linked list just as follows: typedef struct _MYLIST{ int myval; void *next; }MYLIST; MYLIST head;
4
4282
by: FBM | last post by:
Hi, I am working on a program that simulates one of the elements of ATM. The simulation stores events which occurs every some milliseconds for a certain amount of time. Every time that an event is stored in a double linked list, the whole list is sorted for the next round. My problem appears when subjecting the program to heavy load, that is, when I run the simulation for more than 10,000 miliseconds (every event occurs in...
3
1509
by: idshiy | last post by:
hi there i have a linked list content another linked list. which is something like: struct nodebranch{ unsigned int offset; unsigned char data; struct nodebranch *next; }; struct node{
51
8626
by: Joerg Schoen | last post by:
Hi folks! Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.) For linked lists, mergesort is the typical choice. While I was looking for a optimized implementation of mergesort for linked lists, I couldn't find one. I read something about Mcilroy's "Optimistic Merge Sort" and studied some implementation, but they were for arrays. Does anybody know if Mcilroys optimization is applicable to truly linked lists at all?
6
20000
by: askmatlab | last post by:
Hello all: I would like to insert a number into a linked list in ascending order. Is the following function correct? void insert(Node **node, int v) { Node *tmp = (Node *)malloc(sizeof(Node)); while(*node && (*node)->value < v) node = &(*node)->next;
9
4902
by: Sheldon | last post by:
Hi, I am trying to understand linked lists and the different ways to write a linked list and double linked list. I have been trying to get this function called insert_word to work but to no avail. The function receives a string from main and then inserts in the list the new word in alphabetical order. Here is my function: struct word { // double linked list. Here the list is global and is first built
10
6575
by: AZRebelCowgirl73 | last post by:
This is what I have so far: My program! import java.util.*; import java.lang.*; import java.io.*; import ch06.lists.*; public class UIandDB {
0
8626
by: Atos | last post by:
SINGLE-LINKED LIST Let's start with the simplest kind of linked list : the single-linked list which only has one link per node. That node except from the data it contains, which might be anything from a short integer value to a complex struct type, also has a pointer to the next node in the single-linked list. That pointer will be NULL if the end of the single-linked list is encountered. The single-linked list travels only one...
5
12401
by: kylie991 | last post by:
I'm confused as to why this isnt working.. am i doing this right?? I have to create a function that does the following: - Insert a word to the linked list so that the list // remains sorted alphabetically. // PRE: The list is sorted alphabetically or is NULL // POST: The resulting list is sorted alphabetically. If the word is // in the list already, do nothing. struct WordNode { string word;
0
8743
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9102
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
8995
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
7844
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
4417
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4674
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3113
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2424
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
2055
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.