Implementing a matrix class through a hierarchy of Doubly Linked Lists

This is a discussion on Implementing a matrix class through a hierarchy of Doubly Linked Lists within the C++ Programming forums, part of the General Programming Boards category; #I'd write a STL version of the whole thing when needed for any practical use...I'm just trying to grope the ...

  1. #1
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498

    Implementing a matrix class through a hierarchy of Doubly Linked Lists

    #I'd write a STL version of the whole thing when needed for any practical use...I'm just trying to grope the basics through this..

    *I am choosing Doubly linked lists because the matrix would frequently need to remove/add/interchange..etc ..rows & columns.

    && It will typically not go beyond 4*4 order...so access time will be well and good.. Any better Idea?

    The barebone structure of the code would be like:->
    Code:
    class token;
    class node
    {
    	public:
    	token* pre;
    	token t;
    	token* pos; //post
    	//Some funcs to be added as required
    };
    class line  //i.e a single row or column .... 
    {
    	public:
    	node* pre;
    	node n;
    	node* pos;
            //same as above
    };
    class matrix
    {
    
    	
    };
    At this point, I can not imagine what I should put inside the matrix class...
    if I put it in this way..
    Code:
    line* r_pre; // for rows
    line r_l;    
    line* r_pos;
    
    line* c_pre; // for columns 
    line c_l;
    line* c_pos;
    ....I can't figure out how the constructor should behave...
    Finally.. is there a better way to do the whole thing?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  2. #2
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    Matrices are best implemeneted as linear arrays. Matrix concatenation is best implemented as a stack. Most APIs using matrices have matrix stacks. Also keep in mind that matrix concatenation has very specific rules as to which matrices can be concatenated with each other and which ones cannot.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    Quote Originally Posted by manasij7479 View Post
    && It will typically not go beyond 4*4 order...so access time will be well and good.. Any better Idea?
    Yeah... Drop the linked-list idea, seriously.
    A lot of people have proven time and time again that with matrix sizes of not much more than 4x4, or smaller, that a linear array is fastest. Despite how many more operations it may take to switch rows or columns, it's still much faster overall.
    Linked lists should only become involved when it comes to sparse matricies of perhaps 20x20 or larger etc.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    If I use arrays, won't resizing every now and then...make the code very inefficient ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by manasij7479 View Post
    If I use arrays, won't resizing every now and then...make the code very inefficient ?
    Provided you do at least one or two operations between resizing, you'll more than make it up that way.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help with doubly linked lists
    By jjexpress in forum C Programming
    Replies: 4
    Last Post: 12-05-2010, 10:42 AM
  2. Doubly Linked Lists
    By Swerve in forum C++ Programming
    Replies: 6
    Last Post: 03-23-2009, 12:51 PM
  3. Doubly Linked Lists
    By tsut in forum C++ Programming
    Replies: 3
    Last Post: 09-26-2003, 07:53 AM
  4. doubly linked lists
    By AmazingRando in forum C Programming
    Replies: 4
    Last Post: 09-21-2003, 01:57 PM
  5. Doubly Linked Lists ???????
    By Magica in forum C Programming
    Replies: 5
    Last Post: 05-04-2003, 12:14 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21