List Summary

[ghostbody]

We have done a lot of list assignments this semester. Some classmates thinks that it's so hard to do this kind of questions. It seems that only few people will choose my assignment. It's difficult? The answer is yes. It's hard but still reachable.

Inspiration of the issue

A few days ago, it was the first interview of Tencent. One of my classmates went to it but failed. It's because that the interviewer let my classmate to write a doubly-linked-list on the paper and 20 minutes are given. I have some feelings that only if you all classmates practice more in C++ lesson, should you pass the interview. In fact, in all technology interviews, language C/C++ and data structure and algorithm is the basic thing you should know as a software school student.

Understand the philosophy of linked list

This is very important because if you want to implement a class, you need to know what is it first. Why don't we use array? Why need a list?

Some key words: contiguous memory, discrete memory, random access, insertion overhead, deletion overhead.

\ Key words explanation: contiguous memory: A block of memory which is contiguous. discrete memory: Several** blocks of memory which is often not contiguous. random access: Access an element randomly insertion overhead: The overhead usually indicates the time for insert operation. deletion overhead: Similar to insertion overhead.

Array is about contiguous memory while list is about discrete memory.

One important question in programming is that how to store information of the users.

The structure of this is called "data structure".

Both list and array are data structures. But they have different properties. If you are going to store relatively static data which need random read most, array is a good choice. If you are going to store some dynamic content where deletion and insertion is frequently assigned, you should think about list.

Someone will ask, if we need a trade-off, what should we choose? std::deque which is combination of list and array.

How can I finish a problem of list?

We have mentioned two points before:

1. Drafting is very important! Draw the list on a paper is good for you.
2. Be careful when you are meeting the operation on the node of head, you may probably update the "index node".
3. Be careful when you are meeting the operation with a empty list.

For more:

1. When you are implementing the operator=, please be careful according to deep copy and some common problem of this operator.(clear, this = &other and etc.)
2. Be careful when you are doing iterations. For example, find the N-th element of the list.

   About sorting

I see many of you use an array to get all the elements in the list and then sort the array..... This is a stupid method at all. I always hope you to sort the list locally because you will get O(n) space complexity if you make an array. And also, you need time overhead.

There are two methods that I use most:

1. Insertion sort in list It's quite easy, if you know this algorithm in array, you are supposed to try it with a list.

One possible solution in C:

struct ListNode* insertionSortList(struct ListNode* head) {
  if(head == NULL || head->next == NULL) {
    return head;
  }
  struct ListNode * fast = head->next;
  struct ListNode * slow = head;

  while(fast) {
    if(fast->val >= slow->val) {
      fast = fast->next;
      slow = slow->next;
    } else {
      struct ListNode * positioner = head;
      if(fast->val < head->val) {
        slow->next = fast->next;
        fast->next = head;
        head = fast;
      } else {
        while(positioner->next->val <= fast->val) {
          positioner = positioner->next;
        }

        slow->next = fast->next;
        fast->next = positioner->next;
        positioner->next = fast;
      }
      fast = slow->next;
    }
  }
 return head;
}

The core algorithm here is to "swap" small elements to the right position. Well, you see fast and slow pointers, these two pointer can complete many of the list algorithm, if you have a new problem on list, think it first.

Merge sort

You may use this sorting algorithm this week.

Can you use Bubble or other sorting algorithm on this list?

you can discuss it.

STL list

Have a reference to STL list, you job is to read the source code of STL.

https://github.com/ghostbody/15-cpp-learning/blob/master/stl/stl_list.h

It's quite painful to read the source code of STL, but you can try it and you will have a big progress.