Posted By

trusktr on 11/02/11


Tagged

list linked cisp430


Versions (?)

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


 / Published in: C++
 

URL: http://keepskatinbro.com

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 << foobar[3] << endl;

But with my linked list you do:

cout << foobar.get(3) << endl;

With an array:

foobar[2] = 5;

With my Linked List:

foobar.set(2, 5);

The syntax differences are minor, but the usage is just as easy as an array and you don't have to worry about how big your "array" will be.

Keep in mind that you also need to include a single-link node class in your code for use with this linked_list class. I'll post one sometime hehe.

  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. }

Report this snippet  

You need to login to post a comment.