Delete Duplicate Nodes from Linked List

Problem:
Given an unsorted linked list, delete duplicate nodes from the linked list.

Thinking:
This problem is again similar to previous 2 posts (determine uniqueness and remove duplicates). There are several algorithms available.

Node definition:
Suppose the node in this linked list is defined as the class below.

Solution 1:
Without using extra buffer, delete every duplicates for each node encountered. Time complexity \(O(n^2)\).

Solution 2:
Without using extra buffer, each time encountering a node, detect if it's a duplicate. If yes, then delete it. Time complexity \(O(n^2)\).

Solution 3:
Using an extra hash table / hash set / hash map to keep track which nodes have already existed. Average time complexity \(O(n)\).

Notes:

1. Would there be any differences if the linked list is doubly linked?
   ==> Probably not.
2. How about sorting the list first?
   ==> As long as you are allowed to destroy the original order, this should work.

Remove Duplicate Characters

Problem:
Given a string, remove the duplicate characters in the string.

Assumption:
All the characters are from ASCII set and in the range 0~255. Also, the character null character does not appear in the string.

Requirement:
An extra copy of the array is not allowed.

Similar to last post about approaches to deciding unique characters or not, this can be done in place or with an array of fixed size.

Note:
Although C++ algorithm library has unique function, which may seem appropriate for this problem. However, that unique function just removes the consecutive duplicates.

We may also sort the string first if we can remove any duplicates, not necessarily keeping the first one in appearance order. In this way, we may get to time complexity \(O(n\log n)\). Also, this method would destroy the order of unique characters. This solution is not shown in this post.

Solution 1:
For each character in the string and unique, detect all duplicates in the string afterwards. Mark those duplicates and remove them in the end. Suppose the string is given as a char array, otherwise we may need convert a String to StringBuffer, StringBuilder, or CharArray.

Solution 2:
For each character in the string, first determine if it's duplicate. If yes, simply skip it; if not, keep it in the string.

Solution 3:
An extra array of fixed size can be used to record which characters have appeared. This can reduce the time complexity from \(O(n^2)\) to \(O(n)\). Also, we can have boolean array or bitset approaches. Each of them can be applied to the above 2 schemes and we can have 4 different algorithms. Here, I am showing boolean array with Scheme 1 in this solution, and bitset with Scheme 2 for next solution.

Solution 4:
Use bitset with the above Scheme 2 to remove the duplicates.

String Contains All Unique Characters or Not

Problem:
Given a string, determine if this string contains all unique characters.

Assumption:
The characters in this string are from ASCII character set. In other words, the value range is 0~255.

Solution 1:
Directly compare each character in the string with every other character in the string. This approach will take \(O(n^2)\) time and no space.

Solution 2:
If allowed to destroy the string, we may first sort the string using quicksort, and then scan through the string to see if there are 2 adjacent characters are the same. Quicksort will take \(O(n\log n)\) time and \(O(1)\) space. If using mergesort, it will take \(O(n)\) space. In Java, to sort the string, an extra array or StringBuffer is needed.

Solution 3:
Since the characters are in a small range, and we can create an array to record if one certain character has appeared or not. This approach will take \(O(n)\) time and \(O(m)\) space, where \(m\) is the size of character set.

Solution 4:
Similar to Solution 3, but instead of using an array of boolean values, use a set of bits to record the binary values. In Java, \(256/32=8\) int size bits are needed, which can be implemented as an array of 8 integers, and each integer represents 32 characters. In C++, there is a very convenient structure called bitset, which can be beautifully used here.

Notes:
Since the characters are all from the assumed set, and the set size is known. In this case, the maximum length for a string of all unique characters will be the size of the character set. Therefore, for each of the above programs, we may add the following code.

if( s.length() > 256 ) return false;

TreeSet vs HashSet vs LinkedHashSet

The post here nicely summarized the collections TreeSet, HashSet, and LinkedHashSet in Java. I mostly repeat that.

TreeSet	HashSet	LinkedHashSet
public class TreeSet extends AbstractSet implements SortedSet, Cloneable, Serializable	public class HashSet extends AbstractSet implements Set, Cloneable, Serializable	public class LinkedHashSet extends HashSet implements Set, Cloneable, Serializable
unique values	unique values	unique values
red-black tree	hash table	hash table with double links
ascending order	undefined order	insertion order
\(O(\log n)\) for add, remove and contains	\(O(1)\)	\(O(1)\), a littler slower than HashSet except for the operation of iteration

For more details, please see the reference blog.

References:

Vidya's Blog

Size of Class Objects

Some notes about how to determine the size of class objects in C++.

1. The keyword sizeof can work on both class type names and class objects.
2. Static member data don't contribute to the size of class (they are classwide available)
3. Member functions don't really contribute to the size of class (except the vtable for virtual functions).
4. The this pointer doesn't contribute to the size of class objects.
5. Friends and pointers to members are not class members at all, and hence they won't contribute to the class size.
6. It is unspecified whether or not a reference requires storage. It may be compiler specific.
7. The actual size is most likely greater than the sum of sizes for each non-static member data and virtual pointers. This is because of byte alignment or padding, and depends on the compiler.
8. Virtual pointer will take some space if there are virtual functions or virtual inheritance in the class.
9. Empty classes won't be size 0 in order to distinguish the objects of that class type. By most compilers, their size will be 1.
10. Empty sub-objects will take no space in memory when an empty class is inherited by a non-empty class type.
11. Regular inheritance will make the size of derived class the sum of all non-static member sizes from its base classes.
12. The _vptr field is always an alias of the first available _vptr of its base classes, if there are some. Otherwise, the class itself will create a new _vptr if necessary.
13. The virtual inheritance is kind of complex. It's designed to solve the diamond problem in inheritance, and there will be only 1 copy for the common ancestor members. Simply speaking, the class will first create the non-virtual base class members, and its own members in class body, and finally a unique set of members from virtual base classes (including immediate virtual base and inherited virtual base).

References:

C Programming

C++ FAQ

Wikipedia: Reference

Wikipedia: Virtual Inheritance