We discuss how randomization and rank structures can be used in the direct solution of some large dense or sparse linear systems with nearly $O(n)$ complexity and storage. Randomized sampling and related adaptive strategies help significantly improve both the efficiency and the flexibility of structured solution. We also demonstrate how these can be extended to the development of matrix-free direct solvers based on matrix-vector products only. This is especially interesting for problems with few varying parameters (e.g., frequency or shift). We show that such structured solvers also have significantly better stability than classical LU factorizations. They are then very suitable for ill-conditioned problems and can provide solutions with controllable accuracies. Applications to some difficult situations will be demonstrated and the effectiveness will be justified: 1. preconditioning certain indefinite problems where only matrix-vector products are available; 2. solving ill-conditioned Toeplitz least squares problems; 3. finding good initial estimates for iterative (e.g., Newton) eigenvalue solutions.