My linked_list class (both the header file and the template file)


/ Published in: C++
Save to your folder(s)

This is a linked list that can be used like an array where instead of using [] after the reference you just used .get() (and some other methods) but now you don't have to worry about sizing.

For example, with an array you would do:

cout


Copy this code and paste it in your HTML
  1. /*#########################################################
  2. HEADER FILE "linked_list.h":
  3. ###########################################################*/
  4.  
  5. /* Joe Pea - Linked List */
  6.  
  7. #ifndef LINKED_LIST_H
  8. #define LINKED_LIST_H
  9.  
  10. #include <cstdlib> // Provides size_t
  11. #include "node.h" // Provides node class
  12.  
  13. namespace CISP430_A5
  14. {
  15. template <class Item>
  16. class linked_list
  17. /*TODO: * Optimize so that we don't have to iterate through each address to reach a desired position.
  18. Make a "position" field for each Node object or something?
  19. Or create a "last_position" variable in this class so we can iterate forward
  20. or backward from the last position instead of from the beginning each time?
  21. * Add post and pre conditions for all the new functions above.
  22. */
  23. /**
  24. The /*REMOVED*//*, /*STAYS THE SAME*//*, and /*ADDED*//* comments show the
  25. differences in converting from the sequence class to the linked_list class.
  26. */
  27. {
  28. public:
  29. /* TYPEDEFS and MEMBER CONSTANTS: */
  30. typedef Item value_type;
  31. typedef size_t size_type;
  32.  
  33.  
  34.  
  35. /* CONSTRUCTORS and DESTRUCTOR: */
  36. linked_list( );
  37. linked_list(const linked_list& source);
  38. ~linked_list( );
  39.  
  40.  
  41.  
  42. /* MODIFICATION MEMBER FUNCTIONS */
  43. /*ADDED:*/
  44. value_type get(int position); // get item at position x
  45. void set(int position, const value_type& entry); // set item at position x, if past boundaries, just modify at beginning or at end.
  46. void add(const value_type& entry); // add to the end of list
  47. void insert(int position, const value_type& entry); // set item at position x, if past boundaries, just insert at beginning or attach at end.
  48. void attach(int position, const value_type& entry); // set item at position x, if past boundaries, just insert at beginning or attach at end.
  49. void remove(int position);
  50.  
  51. /*REMOVED:*/
  52. /*void remove_current( );*/
  53. /*void start( );*/
  54. /*void advance( );*/
  55. /*void insert(const value_type& entry);*/
  56. /*void attach(const value_type& entry);*/
  57.  
  58. /*STAYS THE SAME:*/
  59. void operator=(const linked_list& source);
  60.  
  61.  
  62.  
  63. /* CONSTANT MEMBER FUNCTIONS */
  64. /*STAYS THE SAME:*/
  65. value_type current( ) const;
  66. size_type size( ) const { return many_nodes; }
  67. bool is_item( ) const { return (cursor != NULL); }
  68.  
  69.  
  70.  
  71. private:
  72. /*PRIVATE HELPER FUNCTIONS*/
  73. /*ADDED:*/
  74. void remove_current( );
  75. void start( );
  76. void advance( );
  77. void insert_here(const value_type& entry); // same as insert() from sequence. insert at current position.
  78. void attach_here(const value_type& entry); // same as attach() from sequence. attach at current position.
  79.  
  80.  
  81.  
  82. /*PRIVATE VARIABLES*/
  83. /*STAYS THE SAME:*/
  84. node<Item> *cursor;
  85. node<Item> *precursor;
  86. node<Item> *head_ptr;
  87. node<Item> *tail_ptr;
  88. size_type many_nodes;
  89. };
  90. }
  91.  
  92.  
  93.  
  94.  
  95.  
  96. /* Sample usage:
  97. int main(void) {
  98.  
  99. linked_list items = new linked_list;
  100. items.attach(10);
  101. items.insert(30);
  102. items.attach(20);
  103. items.insert(40);
  104.  
  105. // for each item in the list:
  106. for (int i=0; i<items.size(); ++i) {
  107. cout << items.get(i) << endl;
  108. }
  109.  
  110. items.set(2, 50);
  111. // item at position 2 is now 50.
  112. }
  113. */
  114.  
  115.  
  116.  
  117.  
  118. // The implementation of a template class must be included in its header file:
  119. #include "linked_list.template"
  120. #endif
  121.  
  122. /*#########################################################
  123. TEMPLATE FILE "linked_list.template":
  124. ###########################################################*/
  125.  
  126.  
  127. /* Joe Pea - CISP430 Assignment 5 */
  128.  
  129. namespace CISP430_A5 {
  130. /*I've marked lines/blocks as REMOVED or ADDED in order to tell what I changed
  131. from the sequence class to create my ideal linked_list class*/
  132. /*TODO: Add previous field to Node class and remove usage of precursor.*/
  133.  
  134. /* CONSTRUCTORS and DESTRUCTOR */
  135.  
  136. template <class Item>
  137. linked_list<Item>::linked_list() {
  138. head_ptr = NULL;
  139. tail_ptr = NULL;
  140. cursor = NULL;
  141. precursor = NULL; // no need for this if Node objects have a "previous" link field.
  142. many_nodes = 0;
  143. }
  144.  
  145. template <class Item>
  146. linked_list<Item>::linked_list( const linked_list& source ) { // copier
  147.  
  148. int src_size = source.size(); // to replicate cursor position
  149. int many_til_end = 0; // to replicate cursor position
  150. int many_til_mid = 0; // to replicate cursor position
  151. node<Item> *src_cursor = source.cursor; // to replicate cursor position
  152.  
  153. list_copy(source.head_ptr, head_ptr, tail_ptr);
  154.  
  155. /*replicate the size value (before cursor position because functions used for that depend on many_nodes value*/
  156. many_nodes = source.many_nodes;
  157.  
  158. /*replicate the cursor position*/
  159. if (src_cursor != NULL) {
  160. while (src_cursor != NULL) {
  161. ++many_til_end;
  162. src_cursor = src_cursor->link();
  163. }
  164. many_til_mid = src_size - many_til_end; // this is how many to advance to replicate cursor position.
  165. start(); // put this.cursor at beginning. // DEPENDS ON VALUE OF many_nodes ABOVE
  166. for (int i=0; i<many_til_mid; ++i) {
  167. advance(); // DEPENDS ON VALUE OF many_nodes ABOVE
  168. }
  169. /* after the for loop, the new linked_list's cursor should be at the same position as the source's cursor was.*/
  170. }
  171. else {
  172. cursor = NULL;
  173. precursor = NULL;
  174. }
  175. }
  176.  
  177. template <class Item>
  178. linked_list<Item>::~linked_list() { // Destructor
  179. list_clear(head_ptr);
  180. head_ptr = tail_ptr = cursor = precursor = NULL;
  181. many_nodes = 0;
  182. }
  183.  
  184. /* MODIFICATION MEMBER FUNCTIONS */
  185.  
  186. template <class Item>
  187. void linked_list<Item>::start() {
  188. if (many_nodes > 0) { // if at least one item exists
  189. cursor = head_ptr;
  190. precursor = NULL;
  191. }
  192. }
  193.  
  194. template <class Item>
  195. void linked_list<Item>::advance() {
  196. if (is_item()) {
  197. precursor = cursor;
  198. cursor = cursor->link();
  199. if ( cursor == NULL ) {
  200. precursor = NULL;
  201. }
  202. }
  203. }
  204.  
  205. /*
  206. ADDED [
  207. */
  208. template <class Item>
  209. typename linked_list<Item>::value_type linked_list<Item>::get(int position) {
  210. for (int i=0; i<=position; ++i) { // advance the cursor to the position then return item
  211. if (i==0)
  212. start();
  213. else
  214. advance();
  215.  
  216. if (i==position) {
  217. return current();
  218. }
  219. }
  220. }
  221.  
  222. template <class Item>
  223. void linked_list<Item>::set(int position, const value_type& entry) {
  224. if (is_item()) { // only set at a valid position.
  225.  
  226. insert(position, entry); // insert new item to list
  227.  
  228. advance();
  229. remove_current(); // remove old item from list.
  230. }
  231. }
  232.  
  233. template <class Item>
  234. void linked_list<Item>::add(const value_type& entry) {
  235. cursor = precursor = NULL; // remove cursor
  236. attach_here(entry); // <<-- attaches at end when no cursor.
  237. }
  238.  
  239. template <class Item>
  240. void linked_list<Item>::remove(int position) {
  241. for (int i=0; i<=position; ++i) { // advance the cursor to the position then insert item
  242. if (i==0)
  243. start();
  244. else
  245. advance();
  246.  
  247. if (i==position) {
  248. remove_current();
  249. }
  250. }
  251. }
  252.  
  253. template <class Item>
  254. void linked_list<Item>::insert(int position, const value_type& entry) {
  255. for (int i=0; i<=position; ++i) { // advance the cursor to the position then insert item
  256. if (i==0)
  257. start();
  258. else
  259. advance();
  260.  
  261. if (i==position) {
  262. insert_here(entry);
  263. }
  264. }
  265. }
  266. /*
  267. ]
  268. */
  269.  
  270. template <class Item>
  271. void linked_list<Item>::insert_here(const value_type &entry) {
  272. /*REMOVED*/
  273. // void linked_list<Item>::insert(const value_type &entry) {
  274.  
  275. /*if the list is empty*/
  276. if (!is_item() && !many_nodes) {
  277. cursor = new node<Item>(entry);
  278. head_ptr = cursor;
  279. tail_ptr = cursor;
  280. }
  281.  
  282. /*if the list is not empty and cursor points to the first item*/
  283. else if (is_item() && cursor == head_ptr) {
  284. cursor = new node<Item>( entry );
  285. cursor->set_link( head_ptr );
  286. head_ptr = cursor;
  287. }
  288.  
  289. /*if the list is not empty and there is no current item*/
  290. else if (!is_item() && many_nodes) {
  291. cursor = new node<Item>( entry );
  292. cursor->set_link( head_ptr );
  293. head_ptr = cursor;
  294. }
  295.  
  296. /*if the list is not empty and the cursor points somewhere in
  297. the middle(including last item)*/
  298. else if (is_item() && cursor != head_ptr) {
  299. cursor = new node<Item>( entry );
  300. cursor->set_link( precursor->link() );
  301. precursor->set_link( cursor );
  302. }
  303.  
  304. ++many_nodes; //increase the node count
  305. }
  306.  
  307. /*ADDED*/
  308. template <class Item>
  309. void linked_list<Item>::attach(int position, const value_type& entry) {
  310. for (int i=0; i<=position; ++i) { // advance the cursor to the position then attach item
  311. if (i==0)
  312. start();
  313. else
  314. advance();
  315.  
  316. if (i==position) {
  317. attach_here(entry);
  318. }
  319. }
  320. }
  321.  
  322. template <class Item>
  323. void linked_list<Item>::attach_here(const value_type& entry) {
  324. /*REMOVED*/
  325. // void linked_list<Item>::attach(const value_type& entry) {
  326.  
  327. /*if the list is empty*/
  328. if (!is_item() && !many_nodes) {
  329. cursor = new node<Item>(entry);
  330. head_ptr = cursor;
  331. tail_ptr = cursor;
  332. precursor = NULL;
  333. }
  334.  
  335. /*if the list is not empty and cursor points to the first item and there's only one item*/
  336. else if (is_item() && many_nodes == 1) {
  337. cursor = new node<Item>( entry );
  338. cursor->set_link( head_ptr->link() );
  339. head_ptr->set_link( cursor );
  340. precursor = head_ptr;
  341. tail_ptr = cursor;
  342. }
  343.  
  344. /*if the list is not empty and cursor points to the first item and there's more than one item*/
  345. else if (is_item() && many_nodes > 1 && cursor == head_ptr ) {
  346. cursor = new node<Item>( entry );
  347. cursor->set_link( head_ptr->link() );
  348. head_ptr->set_link( cursor );
  349. precursor = head_ptr;
  350. }
  351.  
  352. /*if the list is not empty and there is no current item*/
  353. else if (!is_item() && many_nodes) {
  354. cursor = new node<Item>( entry );
  355. tail_ptr->set_link( cursor );
  356. precursor = tail_ptr;
  357. tail_ptr = cursor;
  358. }
  359.  
  360. /*if the list is not empty and the cursor points somewhere in
  361. the middle(including last item)*/
  362. else if (is_item() && cursor != head_ptr) {
  363. if (cursor != tail_ptr) { // if cursor is not at last item
  364. cursor = new node<Item>( entry );
  365. }
  366. else if (cursor == tail_ptr) { // if cursor is at last item
  367. cursor = new node<Item>( entry );
  368. tail_ptr = cursor;
  369. }
  370. cursor->set_link( (precursor->link())->link() );
  371. (precursor->link())->set_link( cursor );
  372. precursor = precursor->link();
  373. }
  374.  
  375. ++many_nodes; // increase the node count
  376. }
  377.  
  378. template <class Item>
  379. void linked_list<Item>::remove_current() {
  380. if ( is_item() ) {
  381.  
  382. /*If the cursor points to an item in the middle of the list, not tail, not head:*/
  383. if (cursor != head_ptr && cursor != tail_ptr) {
  384. precursor->set_link( cursor->link() );
  385. delete cursor;
  386. cursor = precursor->link();
  387. }
  388.  
  389. /*If the cursor points to the first item in the list and that is the only item:*/
  390. else if (many_nodes == 1) {
  391. delete cursor;
  392. cursor = head_ptr = tail_ptr = precursor = NULL;
  393. }
  394.  
  395. /*If the cursor points to the first item in the list and there is more than one item:*/
  396. else if ( cursor == head_ptr && many_nodes > 1) {
  397. cursor = cursor->link();
  398. delete head_ptr;
  399. head_ptr = cursor;
  400. }
  401.  
  402. /*If the cursor points to the last item in the list (and there is more than one item)*/
  403. else if ( cursor == tail_ptr && many_nodes > 1) {
  404. delete cursor;
  405. tail_ptr = precursor;
  406. /* #!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!# */
  407. tail_ptr->set_link(NULL);
  408. /* #!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!# */
  409. precursor = cursor = NULL;
  410. }
  411.  
  412. --many_nodes;
  413. }
  414. }
  415.  
  416. template <class Item>
  417. void linked_list<Item>::operator =(const linked_list& source) {
  418. if (this != &source) {
  419. list_clear(head_ptr);
  420. head_ptr = tail_ptr = cursor = precursor = NULL;
  421. many_nodes = 0;
  422.  
  423. int src_size = source.size(); // to replicate cursor position
  424. int many_til_end = 0; // to replicate cursor position
  425. int many_til_mid = 0; // to replicate cursor position
  426. node<Item> *src_cursor = source.cursor; // to replicate cursor position
  427.  
  428. list_copy(source.head_ptr, head_ptr, tail_ptr);
  429.  
  430. /*replicate the size value (before cursor position because functions used for that depend on many_nodes value*/
  431. many_nodes = source.many_nodes;
  432.  
  433. /*replicate the cursor position*/
  434. if (src_cursor != NULL) {
  435. while (src_cursor != NULL) {
  436. ++many_til_end;
  437. src_cursor = src_cursor->link();
  438. }
  439. many_til_mid = src_size - many_til_end; // this is how many to advance to replicate cursor position.
  440. start(); // put this.cursor at beginning.
  441. for (int i=0; i<many_til_mid; ++i) {
  442. advance();
  443. }
  444. /* after the for loop, the new linked_list's cursor should be at the same position as the source's cursor was.*/
  445. }
  446. else {
  447. cursor = NULL;
  448. precursor = NULL;
  449. }
  450. }
  451. }
  452.  
  453. /* CONSTANT MEMBER FUNCTIONS */
  454.  
  455. template <class Item>
  456. typename linked_list<Item>::value_type linked_list<Item>::current() const {
  457. if ( is_item() ) {
  458. return cursor->data();
  459. }
  460. }
  461.  
  462. }

URL: http://keepskatinbro.com

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.