LinkedHashMap

import java.util.Arrays;
import java.util.LinkedHashSet;

public class Test
{
    public static void main(String[] args)
    {
        LinkedHashSet<Integer> lset = new LinkedHashSet<Integer> ();
        lset.addAll(Arrays.asList(new Integer[] { 4, 1, 2, 3 }));
        System.out.println(lset.toString());
    }
}

4, 1, 2, 3

Conceptual Implementation

// Base class from which LinkedHashMap derives
class HashMap<K,V> implements Map<K,V>
{
    /***********************************************
     * HashMap.Entry class has some methods which are
     * meant to be overridden by derived classes like
     * LinkedHashMap.Entry
     ***********************************************/
    static class Entry<K,V> implements Map.Entry<K,V>
    {
        // Method called from HashMap.put(K)
        void recordAccess(HashMap<K,V> m) {}
        // Method called from HashMap.remove(K)
        void recordRemoval(HashMap<K,V> m) {}
    }


    /*********************************************************
     * HashMap.createEntry is also overridden by LinkedHashMap
     * This allows derived classes to create their own Entry objects
     *********************************************************/
    void createEntry(int hash, K key, V value, int bucketIndex)
    {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;            
    }
}

class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
{
    // Doubly linked list used to maintain the insertion order
    private Entry<K,V> linkedList;
    
    // Boolean to indicate if order of an existing key should be updated
    // with subsequent put() calls for the same key.
    // i.e. if this flag is true, existing entries move to the front of the
    // linked-list when they are put again in the hash-map.
    // This provides behavior like a Least Recently Used (LRU) cache if set to true.
    private final boolean accessOrder;


    /***********************************************
     * LinkedHashMap.Entry extends LinkedHashMap.Entry to
     * add before/after fields of a linked-list
     ***********************************************/
    static class Entry<K,V> extends HashMap.Entry<K,V>
    {
        Entry<K,V> before, after;

        private void remove()
        {
            before.after = after;
            after.before = before;
        }
        
        // Overridden method to record access if
        // LRU behavior is desired
        void recordAccess(HashMap<K,V> m)
        {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder)
            {
                lm.modCount++;
                remove();
                addBefore(lm.linkedList);
            }
        }

        // Overridden method to record removal of an Entry
        void recordRemoval(HashMap<K,V> m)
        {
            remove();
        }
    }

    /*********************************************************
     * Method overridden by LinkedHashMap
     * This allows creation of LinkedHashMap.Entry instead of HashMap.Entry
     *********************************************************/
    void createEntry(int hash, K key, V value, int bucketIndex)
    {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(linkedList);
        size++;
    }
}