catalogue
1. Compilation environment and tools
2. Introduction to double linked list
3. Implementation of double linked list
3.2 Function definition of basic operation
3.3 implementation of basic operation Function
1. Compilation environment and tools
I wrote the program under MAC os and compiled it with GCC. Because it's a little hard to write code in vim, I used VScode as the editor to write makefile s to link multiple files and finally generate an executable program.
2. Introduction to double linked list
First of all, let's talk about why we have a single linked list and a double linked list? When learning single linked list, we all know that compared with array, single linked list has the advantage of being very efficient in adding and deleting data nodes; But it seems stupid to find data. For example, after you find a data node, you want to access the previous data node. At this time, you need to traverse the single linked list again. Of course, you can also use double pointers to do this (we won't consider this for the time being)! In order to improve the efficiency of our linked list in querying data, we add a pointer field to it, which can improve the efficiency of linked list in some data operations. All right! Now let's get to the point!
3. Implementation of double linked list
3.1 definition of data node
The definition of the data node of the double linked list is just one more pointer field than that of the data node of the single linked list. The more pointer field is used to store the precursor of the current data node (that is, the address of the previous node of the current node. Remember, the pointer is the storage address!), Well, let's take a look at the code!
typedef int ElemType;
typedef int Status;
//Data structure definition of double linked list
typedef struct DulNode{
ElemType data; //Data domain
struct DulNode *pre; //Precursor pointer
struct DulNode *next; //Successor pointer
}DulNode;
typedef struct DulNode *DulLinkList; //Define node pointer3.2 Function definition of basic operation
The basic operation of the linked list is nothing more than the old ones. First, you need to create a double linked list! Of course, there are two methods: head interpolation and tail interpolation. Here I use tail interpolation! As for how to implement the head interpolation method, please refer to the head interpolation method in the single linked list for self implementation. ( Single chain header interpolation)
This is the basic operation of traversing, inserting and deleting the whole linked list! The code is as follows:
//Creation of double linked list void CreateDulList(DulLinkList *L, int n); //Traversal of double linked list void DisPlayList(DulLinkList L); //The double linked list inserts the node and inserts the node at the specified position Status InsertNode(DulLinkList *L, int n, ElemType data); //The double linked list deletes the node, deletes the node at the specified location, and returns the data of the deleted node Status DeleteNode(DulLinkList *L, int n, ElemType *data); //Find out whether an element exists in the double linked list Status FindNode(DulLinkList L, ElemType data); //Return linked list length int GetListLength(DulLinkList L);
3.3 implementation of basic operation Function
First of all, let's talk about the creation of double linked list! I have created a header node here! Head - > pre points to NULL, head - > next points to the first node, and head - > data is used to store the length of the linked list. Of course, you can also point your head - > pre to the node, and then point the next node to the head, so as to form a two-way circular linked list. The creation of a double linked list is basically the same as that of a single linked list. It is worth noting that when creating a head node, head - > pre = NULL and head - > next = NULL to avoid the occurrence of wild pointers!
//Creation of double linked list
void CreateDulList(DulLinkList *L, int n)
{
DulLinkList me, ptr;
int i;
(*L) = (DulLinkList)malloc(sizeof(DulNode)); //Apply for space for head node
(*L)->next = NULL;
(*L)->pre = NULL;
(*L)->data = n;
ptr = (*L);
for(i = 0; i < n; i++)
{
me = (DulLinkList)malloc(sizeof(DulNode));
me->data = rand()%100 + 1; //Node data field
me->next = NULL;
me->pre = NULL;
ptr->next = me;
me->pre = ptr;
ptr = ptr->next;
}
}The second is how to traverse the double linked list. In fact, how do you traverse the single linked list? Here you can traverse the double linked list!
//Traversal of double linked list
void DisPlayList(DulLinkList L)
{
DulLinkList me;
me = L->next;
for(;me != NULL; me = me->next)
{
printf("%d ",me->data);
}
printf("\n");
}To insert a new node at the specified location, you need to pay attention. First, you need to judge whether the inserted location is legal! When the insertion position is legal, you need to consider whether to insert in front of the first node. If you insert in front of the first node, you need to deal with it separately (as for why to deal with it separately, it's because the code I wrote is unreasonable!), The second is the insertion of the normal position! OK, let's take a look at the code!
//The double linked list inserts the node and inserts the node at the specified position
Status InsertNode(DulLinkList *L, int n, ElemType data)
{
DulLinkList me,ptr,prev;
me = (DulLinkList)malloc(sizeof(DulNode));
me->data = data;
me->pre = NULL;
me->next = NULL;
ptr = (*L)->next;
if(n < 1 || n > (*L)->data)
{
printf("insert location is error! please check your insert location.\n");
return ERROR;
}
else if(n == 1) //Insert header
{
me->next = ptr;
ptr->pre = me;
(*L)->next = me;
me->pre = (*L);
((*L)->data)++;
return OK;
}
else{
for(int i = 0; i < n; i++)
{
prev = ptr;
ptr = ptr->next;
}
me->next = ptr;
ptr->pre = me;
prev->next = me;
me->pre = prev;
((*L)->data)++;
return OK;
}
}Deleting a node at a specified location is actually similar to inserting a node at a specified location! Well, more nonsense, let's look at the code! (remember! Remember! Remember! Say the important words three times! That is the deleted node. Don't not release the memory! Otherwise, the memory leaks, which is a big problem!)
//The double linked list deletes the node, deletes the node at the specified location, and returns the data of the deleted node
Status DeleteNode(DulLinkList *L, int n, ElemType *data)
{
DulLinkList me,ptr;
me = (*L);
if(n < 1 || n > (me->data))
{
printf("delete location is error! please check your delete location.\n");
return ERROR;
}
else if(n == 1)
{
ptr = me->next;
me->next = ptr->next;
ptr->next->pre = me;
*data = ptr->data;
free(ptr);
((*L)->data)--;
return OK;
}
else{
me = me->next;
for(int i = 1; i < n; i++)
{
ptr = me;
me = me->next;
}
ptr->next = me->next;
me->next->pre = ptr;
(*data) = me->data;
free(me);
((*L)->data)--;
return OK;
}
}The next step is how to search the double linked list for whether the data node is in the linked list! This is the same as the single linked list, so I won't say anything! Paste code directly! Just look!
//Find out whether an element exists in the double linked list
Status FindNode(DulLinkList L, ElemType data)
{
DulLinkList me;
int Location = 1;
me = L->next;
for(; me != NULL; me = me->next, Location++)
{
if(data == me->data)
break;
else
continue;
}
if(Location < L->data)
return Location;
else
return ERROR;
}All right! This is the end of the article! Do you make complaints about wanting to Tucao Bo bloggers? Take a look at this blogger. He posts code all the time and doesn't say anything! It's not that I don't talk! It's really nothing to say. If you understand the single linked list, of course you will understand the double linked list! (what are you thinking? Ha ha!) Feel it for yourself!
4. Preparation of makefile
I said at the beginning of the article! Why should I use makefile! Because vscode people will not automatically help you link the files you use. It will only make a single file run! (lie to you. In fact, he can also get multiple files to compile, but you need to manually add them to the configuration file. As for how to do it, there are a lot of online tutorials and Baidu by yourself. If Baidu doesn't want Baidu, I advise you to be kind!), Here, I myself have been practicing writing makefile files deliberately recently, which may not be very good! The level of primary makefile ha! However, I think makefile is very interesting. To build stm32 development environment on linux in the future, the writing of makefile is essential. Therefore, everything has a reason! Well, look at what my makefile looks like! My Makefile, you may be able to use it directly with linux, mac os, but windows may not work!
#OBJS=main.o double_list.o CC=gcc CFLAGS+=-c -Wall -g TOPDIR := $(PWD) OBJDIR := $(TOPDIR)/build BINDIR := $(TOPDIR)/bin SRCDIR := $(TOPDIR)/src sfStack: $(OBJDIR)/main.o $(OBJDIR)/double_list.o $(CC) $^ -o $@ $(OBJDIR)/%.o:$(SRCDIR)/%.c $(CC) $^ $(CFLAGS) -o $@ run: ./sfStack clean: $(RM) $(OBJDIR)/*.o sfStack -r help: @echo "********************************* help *******************************" @echo "* *" @echo "* option description *" @echo "* *" @echo "********************************* help *******************************" clear: clear
5. Summary
This article has some water. Just drink less! By the way, if there is a great God who writes makefile s, let me ask you a question! Is how to put the compiled executable file into the folder you specify? Welcome to leave a message in the comment area! At the same time, welcome all visitors to praise! (it's just food! A person who likes to play with food!) The