“This is the third day of my participation in the August More Text Challenge. For details, see: August More Text Challenge.”

Follow me for more updates

Data structure and algorithm (I): time complexity and space complexity

Data structure and algorithm (2): stack

Data structure and algorithm (3): queue

Data structure and algorithm (4): single linked list

Data structure and algorithm (5): two-way linked list

Data structure and algorithm (6): hash table

Data Structures and algorithms (7): trees

Data Structure and algorithm (8): sorting algorithm

Data Structures and algorithms (9): classical algorithm interview questions

The list is introduced

A linked list is a common basic data structure. It is a linear list, but does not store data in a linear order. Instead, each node stores a pointer to the next node. Because they are not necessarily contiguously stored, linked lists can be inserted at O(1) complexity, much faster than sequential tables (such as arrays), but it takes O(n) time to find a node or access a specific number of nodes, whereas sequential tables have O(logn) and O(1) time to insert and query, respectively.

The storage characteristics of the linked list in memory are as follows:

  1. The nodes of a linked list are not necessarily contiguously stored, so you can make full use of the fragmented space in memory.

  2. The linked list is stored in the way of nodes, which is chain storage;

  3. A linked list is implemented by nodes. Each node contains the data field and the next field. Data stores valid data and can be of any type. Next points to the next node;

  4. Because nodes can be created dynamically, there is no logical limit to the length of a linked list;

  5. The linked list can be divided into the linked list with a leading node and the list without a leading node, which can be selected according to the actual requirements

Linked lists vs arrays

Array:

  • Find fast, add/delete slow.
  • The storage space is fixed. If the storage space is insufficient, you need to expand the storage space. Once the storage space is expanded, data replication is required, which takes a lot of time.

List:

  • Find slow, add/delete fast.
  • Memory consumption is higher because each node in the list consumes additional storage space to store Pointers to the next node. Frequent insertion and deletion of linked lists cause frequent memory application and release, which may easily cause memory fragmentation.

Common species list structure

  • Singly linked list
  • Two-way linked list
  • Circular linked list
  • Block list
  • Other extensions

This article mainly introduces the single linked list to add, delete, change and check

Single linked list of additions and deletions

  1. Insert node:

    There are two kinds of insertion. one is inserted at the end of the list, and the other is inserted in the middle. In the middle of the insertion is divided into the insertion before the specified node and the insertion after the specified node, relatively complex; This paper adopts the tail insertion method, which can ensure that the output is output according to the insertion sequence.

    End of queue insertion logic: use the while loop to find the end node, then insert :current.next = newNode

  2. Remove nodes

    First judge whether the list is empty, if it is empty, return directly; If the value is not empty, delete it.

    In the delete logic, a flag is defined to indicate whether the node to be deleted is found. If ([current.next. Data.id isEqualToString: stu.id])), if ([current.next. Data.id])), if ([current.next If flag is YES, direct break; After the traversal is complete, determine the flag. If the flag is YES, delete the node. If the flag is NO, “The node is not found and cannot be deleted” is displayed. Delete code :current.next = current.next

  3. Modify the node

    Check whether the list is empty. If the list is empty, return the value directly. If not, perform the modification logic.

    Modify logic: First define a flag to mark whether the node to be modified is found. Use the while loop to find the node to be modified. If it is found, set the flag to YES and break directly. After the traversal is complete, determine the flag. If the value is YES, modify the flag. If the value is NO, “The node is not found and cannot be modified” is displayed. Modified code :current.data.name = newele.name

  4. Query list

    Check whether the list is empty. If the list is empty, the query is returned. If not, the query logic is executed. Query logic: Use a while loop to iterate through the output

SingleLinkList. H file

// Built-in class :LinkNode @interface LinkNode: NSObject /**data can be any type */ @Property (nonatomic,strong) Student *data; /** Point to next element */ @property (nonatomic,strong) LinkNode *_Nullable next; - (instancetype)initWithData:(Student*_Nullable)data; @end @interface SingleLinkList: NSObject /** List head node */ @property (nonatomic,strong) LinkNode * head; -(BOOL)isEmpty; -(void)add:(Student*)stu; */ -(BOOL)addByOrder:(Student*)stu; // addByOrder:(Student*)stu; -(void)del:(Student*)stu; -(void)updateNode:(Student*)node newNode:(Student*)stu; -(void)show; @endCopy the code

SingleLinkList. M file

//LinkNode @implementation LinkNode - (instanceType)initWithData (Student*)data {self = [super init]; if (self) { self.data = data; } return self; } @end @implementation SingleLinkList - (instancetype)init { self = [super init]; if (self) { self.head = [[LinkNode alloc]initWithData:nil]; } return self; } -(BOOL)isEmpty{ return self.head.next == NULL; } -(void)add:(Student*)stu{ LinkNode*newNode = [[LinkNode alloc]initWithData:stu]; LinkNode*current = self.head; while (current.next) { current = current.next; } current.next = newNode; } /** return 1 for successful insertion, 0 for failed insertion, already has the same id */ -(BOOL)addByOrder:(Student*)stu{LinkNode*newNode =  [[LinkNode alloc]initWithData:stu]; BOOL flag = YES; LinkNode*current = self.head; LinkNode*current = self.head; while (current.next) { if ([stu.ID intValue] < [current.next.data.ID intValue]) { break; }else if([stu.id intValue] == [current.next. Data.id intValue]){flag = NO; // If the same id exists, then break cannot be inserted; } current = current.next; } if (flag) {// insert into the correct position newNode.next = current.next; current.next = newNode; }else{printf(" cannot insert \n with the same id "); } return flag; } -(void)del:(Student*)stu{// if (self.head.next == NULL) {printf(" the list is empty and cannot be deleted \n"); return; BOOL flag = NO; BOOL flag = NO; BOOL flag = NO; LinkNode*current = self.head; while (current.next) { if ([current.next.data.ID isEqualToString:stu.ID]) { flag = YES; // The last node to be deleted is found break; } current = current.next; } if (flag) { current.next = current.next.next; // Delete the node}else{printf(" the data \n was not found "); }} -(void)updateNode:(Student*)newEle{// check whether the list is null if ([self isEmpty]) {printf(" list is null, \n"); return; } BOOL flag = NO; BOOL flag = NO; LinkNode*cur = self.head.next; while (cur) { if ([cur.data.ID isEqualToString:newEle.ID]) { flag = YES; cur.data.name = newEle.name; break; } cur = cur.next; } if (! Flag) {printf(" not found, cannot modify "); }} -(void)show{printf(" print list :"); If ([self isEmpty]) {printf(" list isEmpty \n"); return; } LinkNode*current = self.head; while (current.next ! = NULL) { current = current.next; printf("%s-->",current.data.ID.UTF8String); } printf("\n"); } @endCopy the code

This is a single linked list of the test code

-(void)singleLinkListCase{ SingleLinkList*linkedList = [SingleLinkList new]; [linkedList del:[[Student alloc]initWithID:@"2" name:@" red "]]; // Print the queue [linkedList show]; [linkedList add:[[Student alloc]initWithID:@"1" name:@" min "]]; [linkedList add:[[Student alloc]initWithID:@"2" name:@" red "]]; [linkedList add:[[Student alloc]initWithID:@"3" name:@" jun "]]; [linkedList add:[[Student alloc]initWithID:@"4" name:@" country "]]; [linkedList addByOrder:[[Student alloc]initWithID:@"0" name:@"a"]]; [linkedList addByOrder:[[Student alloc]initWithID:@"6" name:@"b"]]; [linkedList addByOrder:[[Student alloc]initWithID:@"5" name:@"c"]]; [linkedList addByOrder:[[Student alloc]initWithID:@"0" name:@"a"]]; [linkedList show]; [linkedList del:[[Student alloc]initWithID:@"2" name:@" red "]]; [linkedList del:[[Student alloc]initWithID:@"1" name:@" min "]]; [linkedList show]; [linkedList del:[[Student alloc]initWithID:@"1" name:@" min "]]; [linkedList show]; }Copy the code

Pay attention to my

If you think I wrote a good, please point to follow me your support is my more the biggest motivation!