Thread: Implementing a matrix class through a hierarchy of Doubly Linked Lists

  1. #1
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657

    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?

  2. #2
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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,318
    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
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    If I use arrays, won't resizing every now and then...make the code very inefficient ?

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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, 11: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