Technologies used in aviation must provide strict performance guarantees, which delays the introduction of new technologies. Consequently, analog voice communication has remained widely deployed in avionic communications systems. As the number of airplanes keeps growing, inefficient spectral utilization is pushing these systems to their limits, and the lack of encrypted, digital communication is concerning. This dissertation focuses on extending the L-band Digital Aeronautical Communications System (LDACS) with the Air-Air (A/A) mode, creating an Aeronautical Ad-hoc Network that dynamically connects highly mobile aircraft, and practically extends Air-Ground (AG) coverage. A Medium Access Control (MAC) protocol is proposed for LDACS A/A, which is evaluated on the busiest oceanic airspace, the North Atlantic Corridor. The proposed protocol is a distributed algorithm that allows LDACS A/A users to self-organize their channel access without any infrastructure support. In particular, it achieves a guaranteed average packet reception rate in the worst case, solves the hidden node problem and meets pre-determined latency and throughput bounds for dedicated point-to-point links. LDACS must share its assigned spectrum with several legacy radio systems such as the Distance Measuring Equipment (DME). A Machine Learning (ML) algorithm is iteratively designed and evaluated to learn the legacy system's channel access and predict future channel accesses. The results demonstrate that LDACS A/A can reliably and opportunistically co-utilize frequency channels that are actively used by DME. Overall, this thesis proposes a novel, distributed aeronautical MAC protocol and an ML-based algorithmic approach to radio system coexistence in the same frequency band.