I told Lydia to wait so I could go kill a dragon because I didn't want her being killed. She wasn't in a cave. She was in a witch's hut. I slowly made my way back to her (because I was over my carry weight) and she was gone. This has happened before but she just popped back up. I've waited for her and she hasn't popped back up or returned to Dragonsreach. Is there a way to get her back? Or can she die if she's not with me? I'm playing on the PS3.
If you don't have a mod to prevent it she can be killed. Any follower can. If she was attacked wherever you left her she will move around as she fights. If she lives she will the stand in her last location and may not be easy to find. When Followers get tired of waiting for you they go "home" wherever home is for you.
Also try fast traveling from one hold to another. If she's alive she'll show up after a couple of these. If you fast travel through several holds and she doesn't show up you have my condolences. On xbox I use a mod called "No More Dead Followers". Maybe its on PS3.