By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,768 Members | 2,054 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,768 IT Pros & Developers. It's quick & easy.

Linked list questions

P: 1
How do i keep a linked list sorted? How do i remove if more than 10 items?

Expand|Select|Wrap|Line Numbers
  1. from node import node
  2.  
  3. probe = head
  4. count = 0
  5. while probe != None:
  6.     count += 1
  7.     probe = probe.next
  8. return count
  9.  
  10. def insert(newName, newScore, head):
  11.     probe.next.score = newScore
  12.     if head is None:
  13.         head = newNode
  14.     else:
  15.         probe = head
  16.         while probe.next != None:
  17.                 probe = probe.next
  18.                 probe.next = newNode
  19.     return head
  20.  
  21. def printStructure(newName, newScore):
  22.     probe = head
  23.     while probe != None:
  24.         print "Name: ", probe.name,
  25.         print "Score: ", probe.score
  26.         probe = probe.next
  27.  
  28. def main():
  29.     head  = None
  30.  
  31.     head = insert("She-RA", 1088, head)
  32.     printStructure(head)
  33.  
  34.     #Add ten nodes to the beginning of the linked structure
  35.     head = insert("He-MAN", 32464, head)
  36.     head = insert("Doc-Ock", 143322, head)
  37.     head = insert("Spidey", 6416, head)
  38.     head = insert("Superman", 63438, head)
  39.     head = insert("Arceus", 92515, head)
  40.     head = insert("Batman", 11986, head)
  41.     head = insert("Homer", 26712, head)
  42.     head = insert("F-ZERO", 833849, head)
  43.     insert("Dlew58", 999999, head)
  44.     print "Top Ten"
  45.     printStructure(head)
  46. if __name__ == "__main__":
  47.     main()
  48.  
Dec 20 '10 #1
Share this Question
Share on Google+
1 Reply


Expert 100+
P: 624
A linked list is not sorted, it is linked in some order. So if you have records with the values 'A', 'C', 'E', 'G', 'H' in the linked list and you wanted to add 'B', the next record number would then be 6, so record number 1 would point to 6 instead of 2, and record 6 would point to the second record to keep them in order.
How do i remove if more than 10 items?
It depends on if you are talking about memory or a file on disk. Generally you mark it as deleted, and simply remove the link to it, so the record that points to it would point to the record that it used to point to. Practically speaking, regenerating the linked list isn't necessary every time a record is deleted but is done after some threshold is reached. To regenerate the linked list, you would copy the records in the original list to a new memory location or file without copying the deleted records.
Dec 21 '10 #2

Post your reply

Sign in to post your reply or Sign up for a free account.