Created
November 13, 2012 19:11
-
-
Save dautermann/4067743 to your computer and use it in GitHub Desktop.
LinkedList implementation in Objective C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // instructions for actually running & trying this out are at the bottom of this file... | |
| @interface LList : NSObject | |
| { | |
| NSInteger _currentValue; | |
| LList * _next; | |
| } | |
| - (void) insert: (NSInteger) valueToInsert; | |
| - (void) printValue; | |
| - (LList *) reverseLinkedList; | |
| @property (readwrite) NSInteger currentValue; | |
| @property (retain) LList * next; | |
| @end | |
| @implementation LList | |
| @synthesize currentValue = _currentValue; | |
| @synthesize next = _next; | |
| // doing the below assignment allows us to insert a zero into the linked list | |
| // if desired... | |
| #define kNotYetSet NSIntegerMin | |
| // there's also a NSNotFound enum, but that's set to NSIntegerMax so that | |
| // would break our algorithm below | |
| // creates a LList object with no value and no payload and a nil object for next | |
| - (id) init | |
| { | |
| self = [super init]; | |
| if(self) | |
| { | |
| _currentValue = kNotYetSet; | |
| // no need to do this, since Objective C does it automagically | |
| // but just to make it clear... | |
| _next = NULL; | |
| } | |
| return(self); | |
| } | |
| - (void) insert: (NSInteger) valueToInsert | |
| { | |
| // look at the next value (if it exists) and see if there is the right place to insert a new LinkedList node | |
| LList * nextNode = self.next; | |
| LList * newNode; | |
| if(self.currentValue == kNotYetSet) | |
| { | |
| self.currentValue = valueToInsert; | |
| return; | |
| } | |
| if(valueToInsert < self.currentValue) | |
| { | |
| newNode = [[LList alloc] init]; | |
| if(newNode) | |
| { | |
| newNode.currentValue = self.currentValue; | |
| newNode.next = self.next; | |
| self.currentValue = valueToInsert; | |
| self.next = newNode; | |
| } | |
| return; | |
| } | |
| if(nextNode == NULL) | |
| { | |
| // nothing is next, so this is the place to insert the new LinkedList node | |
| newNode = [[LList alloc] init]; | |
| if(newNode) | |
| { | |
| newNode.currentValue = valueToInsert; | |
| // no need to reset "next" for the newNode, since this is the new tail of the LinkedList | |
| self.next = newNode; | |
| return; | |
| } | |
| } else { | |
| // see if the value we're trying to insert fits between the current and the next value | |
| if((valueToInsert >= self.currentValue) && (valueToInsert < nextNode.currentValue)) | |
| { | |
| newNode = [[LList alloc] init]; | |
| if(newNode) | |
| { | |
| newNode.currentValue = valueToInsert; | |
| newNode.next = nextNode; | |
| self.next = newNode; | |
| } | |
| } else { | |
| [nextNode insert: valueToInsert]; | |
| } | |
| } | |
| } | |
| - (void) printValue | |
| { | |
| LList * nextNode = self.next; | |
| NSLog( @"%ld", self.currentValue); | |
| if(nextNode) | |
| { | |
| // keep going down the list | |
| [nextNode printValue]; | |
| } | |
| } | |
| - (LList *) reverseLinkedList | |
| { | |
| // walk to the end of the linked list, reversing things as we go | |
| LList *curNode = self; | |
| LList *prevNode = nil; | |
| LList *nextNode; | |
| while(curNode) { | |
| nextNode = curNode.next; | |
| curNode.next = prevNode; | |
| prevNode = curNode; | |
| curNode = nextNode; | |
| } | |
| // and return the new top of the list (which was the previous end of the list) | |
| return(prevNode); | |
| } | |
| @end | |
| // and put this into a main.m | |
| #import <Foundation/Foundation.h> | |
| #import "LList.h" | |
| int main(int argc, const char * argv[]) | |
| { | |
| @autoreleasepool { | |
| LList * list = [[LList alloc] init]; | |
| [list insert:10]; | |
| [list insert:20]; | |
| [list insert:5]; | |
| [list insert:30]; | |
| [list insert:12]; | |
| [list printValue]; | |
| // and to reverse the list and print it... | |
| list = [list reverseLinkedList]; | |
| [list printValue]; | |
| } | |
| return 0; | |
| } | |
| // and here's the output | |
| 2012-11-13 11:16:47.733 LinkedListTest[10318:303] 5 | |
| 2012-11-13 11:16:47.733 LinkedListTest[10318:303] 10 | |
| 2012-11-13 11:16:47.733 LinkedListTest[10318:303] 12 | |
| 2012-11-13 11:16:47.734 LinkedListTest[10318:303] 20 | |
| 2012-11-13 11:16:47.734 LinkedListTest[10318:303] 30 | |
| 2014-10-07 10:24:59.901 LinkedList[27139:303] 30 | |
| 2014-10-07 10:24:59.901 LinkedList[27139:303] 20 | |
| 2014-10-07 10:24:59.902 LinkedList[27139:303] 12 | |
| 2014-10-07 10:24:59.902 LinkedList[27139:303] 10 | |
| 2014-10-07 10:24:59.903 LinkedList[27139:303] 5 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment