@@ -44,3 +44,115 @@ LRUCache.prototype.put = function (key, value) {
4444}
4545this . cacheMap . set ( key , value ) ;
4646} ;
47+
48+ //////////////////////////////////////////////////////////////////////////////
49+ // JavaScript Object Class Implementation
50+ // This solution requires more code and space due to the need to separately
51+ // define a doubly linked list and a hash map, but has better performance due
52+ // to strictly maintaining constant time lookups and additions.
53+ //////////////////////////////////////////////////////////////////////////////
54+
55+ class LRUNode {
56+ /**
57+ *@param {number } key
58+ *@param {number } val
59+ *@param {LRUNode= } next = `null`
60+ *@constructor
61+ */
62+ constructor ( key , val , next = null ) {
63+ this . key = key ;
64+ this . val = val ;
65+ this . prev = null ;
66+ this . next = next ;
67+ }
68+ }
69+
70+ class LRUCache {
71+ /**
72+ *@param {number } capacity
73+ *@constructor
74+ */
75+ constructor ( capacity ) {
76+ this . head = null ;
77+ this . tail = null ;
78+ this . map = Object . create ( null ) ;
79+ this . length = 0 ;
80+ this . capacity = capacity ;
81+ }
82+
83+ /**
84+ *@param {number } key
85+ *@return {number }
86+ */
87+ get ( key ) {
88+ if ( ! ( key in this . map ) ) {
89+ return - 1 ;
90+ }
91+ this . makeMostRecent ( key ) ;
92+ return this . map [ key ] . val ;
93+ }
94+
95+ /**
96+ *@param {number } key
97+ *@param {number } val
98+ *@return {void }
99+ */
100+ put ( key , val ) {
101+ if ( key in this . map ) {
102+ this . map [ key ] . val = val ;
103+ this . makeMostRecent ( key ) ;
104+ return ;
105+ }
106+
107+ if ( this . length === this . capacity ) {
108+ delete this . map [ this . tail . key ] ;
109+ if ( this . head === this . tail ) {
110+ this . head = null ;
111+ this . tail = null ;
112+ } else {
113+ this . tail = this . tail . prev ;
114+ this . tail . next = null ;
115+ }
116+ } else {
117+ ++ this . length ;
118+ }
119+
120+ const node = new LRUNode ( key , val , this . head ) ;
121+
122+ if ( this . head ) {
123+ this . head . prev = node ;
124+ } else {
125+ this . tail = node ;
126+ }
127+ this . head = node ;
128+
129+ this . map [ key ] = node ;
130+ }
131+
132+ /**
133+ *@param {number } key
134+ *@return {void }
135+ */
136+ makeMostRecent ( key ) {
137+ const node = this . map [ key ] ;
138+
139+ if ( node === this . head ) {
140+ return node . val ;
141+ }
142+
143+ if ( node . prev ) {
144+ node . prev . next = node . next ;
145+ }
146+ if ( node . next ) {
147+ node . next . prev = node . prev ;
148+ }
149+ if ( node === this . tail ) {
150+ this . tail = node . prev ;
151+ }
152+
153+ node . prev = null ;
154+ node . next = this . head ;
155+ this . head . prev = node ;
156+ this . head = node ;
157+ }
158+ }