Sachverhalt:
A.
In der Nacht vom 16. auf den 17. März 2013 war X._ zusammen mit seinen Freunden B._ und C._ im Ausgang. Später stiessen sie auf D._ und A._, den Cousin von C._. B._ anerbot, sie alle nach Hause zu fahren. Auf der Fahrt zum Wohnort von C._ machte sich der alkoholisierte A._, ein langjähriger Freund von X._, ständig über dessen Stottern lustig. Die anderen lachten ebenfalls. X._ bat sie vergeblich, damit aufzuhören. Schliesslich schlug X._ erbost zweimal den linken Ellbogen oder die linke Hand ins Gesicht von A._, worauf dieser mit Händen und Füssen zurückschlug und -trat. Daraufhin hielt B._ an und zerrte A._ aus dem Wagen. Dieser rannte um das Fahrzeug herum, riss die Beifahrertüre auf und schlug und trat erneut auf den in diesem Zeitpunkt immer noch angegurteten X._ ein. X._ stieg in der Folge ebenfalls aus dem Fahrzeug und es kam zu einer körperlichen Auseinandersetzung zwischen den beiden. Ihre Freunde versuchten erfolglos, dies zu verhindern. X._ wird vorgeworfen, im Verlauf der Auseinandersetzung ein Klappmesser mit ca. 5.5 bis 6 cm Klingenlänge behändigt, dieses geöffnet und damit vor dem Gesicht von A._ herumgefuchtelt zu haben. Dabei habe er A._ eine oberflächliche ritzerartige Hautläsion an der linken Ohrmuschel zugefügt. A._ habe daraufhin den rund 20 cm kleineren, viel leichteren und ihm damit körperlich weit unterlegenen X._ in den Schwitzkasten genommen, indem er dessen Kopf unter seinem linken Arm eingeklemmt habe, so dass X._ bei gebeugter Haltung mit dem Kopf gegen die Rückseite von A._, das Gesicht nach unten, fixiert gewesen sei. Aus dieser Stellung habe X._ A._ mit dem immer noch offenen Messer in den Rücken gestochen, wodurch dieser eine 1 cm lange und 2 cm tiefe, von links oben nach rechts unten verlaufende Stichverletzung auf Höhe der 10. Rippe erlitten habe. In der Folge sei es den Anwesenden gelungen, die beiden Kontrahenten zu trennen und X._ das Messer wegzunehmen.
B.
Das Strafgericht des Kantons Basel-Stadt sprach X._ am 28. Mai 2015 der versuchten vorsätzlichen Tötung und der einfachen Körperverletzung mit einem gefährlichen Gegenstand schuldig und verurteilte ihn zu 31⁄2 Jahren Freiheitsstrafe, unter Anrechnung der erstandenen Untersuchungshaft.
C.
Auf Berufung von X._ hin sprach ihn das Appellationsgericht des Kantons Basel-Stadt am 26. Oktober 2016 der versuchten schweren Körperverletzung im nicht entschuldbaren Notwehrexzess und der einfachen Körperverletzung mit einem gefährlichen Gegenstand schuldig und verurteilte ihn zu einer bedingten Freiheitsstrafe von 2 Jahren, unter Anrechnung der Untersuchungshaft.
D.
X._ führt Beschwerde in Strafsachen mit den Anträgen, es sei das Urteil des Appellationsgerichts vom 26. Oktober 2016 aufzuheben und er sei vollumfänglich freizusprechen. Eventualiter sei die Angelegenheit zu neuer Entscheidung an die Vorinstanz zurückzuweisen.
Das Appellationsgericht verzichtet auf eine Vernehmlassung und beantragt die Abweisung der Beschwerde. Die Staatsanwaltschaft des Kantons Basel-Stadt ersucht um Abweisung der Beschwerde, soweit darauf einzutreten sei. A._ hat sich innert Frist nicht vernehmen lassen. X._ machte von seinem Replikrecht Gebrauch und hält an seinen Anträgen fest.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt, die vorinstanzliche Sachverhaltsfeststellung hinsichtlich der Schnittverletzung am Ohr sei willkürlich und verstosse gegen den Grundsatz "in dubio pro reo". Es lasse sich nicht erstellen, zu welchem Zeitpunkt während der Auseinandersetzung die Verletzung entstanden sei. Aufgrund dieser Unsicherheit müsse zu seinen Gunsten davon ausgegangen werden, dass die Schnittwunde entstand, während der Beschwerdegegner ihn in den Schwitzkasten nahm, womit auch die Verletzung am Ohr durch Notwehr gerechtfertigt sei.
1.1.1. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig, das heisst willkürlich im Sinne von <ref-law> ist (<ref-ruling> E. 1.3.1 mit Hinweis; zum Begriff der Willkür: <ref-ruling> E. 1.2; <ref-ruling> E. 2.1; je mit Hinweisen), oder wenn sie auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Eine entsprechende Rüge muss klar vorgebracht und substanziiert begründet werden (<ref-law>). Auf rein appellatorische Kritik am angefochtenen Urteil tritt das Bundesgericht nicht ein (<ref-ruling> E. 5.4, 369 E. 6.3; je mit Hinweisen).
Ob der Grundsatz "in dubio pro reo" als Beweiswürdigungsregel verletzt ist, prüft das Bundesgericht unter dem Gesichtspunkt der Willkür (<ref-ruling> E. 7 mit Hinweisen; Urteil 6B_253/2016 vom 29. März 2017 E. 1.3.2 mit Hinweisen).
1.1.2. Die Vorinstanz erwägt, der von der Erstinstanz festgestellte Sachverhalt sei in objektiver Hinsicht weitgehend unbestritten und durch die objektiven Beweismittel sowie die schlussendlich im Wesentlichen übereinstimmenden respektive miteinander korrespondierenden Aussagen der Beteiligten - namentlich jene von B._, welcher als Einziger in jener Nacht keinen Alkohol konsumiert und das Geschehen aus nächster Nähe mitbekommen habe - nachgewiesen. Demnach habe der Beschwerdeführer die ihm zur Last gelegten Tathandlungen von Anfang an eingestanden. Er habe auch ausgesagt, das Messer aus seiner Umhängetasche genommen und mit dem gestreckten Arm vor dem Beschwerdegegner herumgefuchtelt zu haben, um diesen auf Abstand zu halten. Dabei habe er den Beschwerdegegner wahrscheinlich am Ohr verletzt. Wie der Beschwerdeführer unter Verweis auf die Depositionen der Beteiligten aufzeigt, ist es zutreffend, dass diese keine genauen Angaben zur Verletzung am Ohr des Beschwerdegegners machen konnten. Dass die Verletzung auch zu einem anderen Zeitpunkt während der Auseinandersetzung entstanden sein könnte, lässt sich zwar nicht mit Sicherheit ausschliessen. Dass eine andere Lösung oder Würdigung ebenfalls vertretbar oder gar zutreffender erscheint, genügt für die Annahme von Willkür allerdings nicht (<ref-ruling> E. 1.2 mit Hinweisen). Gestützt auf die erwähnten Aussagen - und zwar insbesondere diejenigen des Beschwerdeführers selber - ist die vorinstanzliche Feststellung, die Verletzung am Ohr sei während des Herumfuchtelns mit dem Messer entstanden, nicht geradewegs willkürlich. Somit verletzt die vorinstanzliche Sachverhaltsfeststellung kein Bundesrecht.
1.2. Der Beschwerdeführer ist der Ansicht, selbst wenn von der vorinstanzlichen Sachverhaltsfeststellung ausgegangen würde, wäre die Verletzung am Ohr des Beschwerdegegners von der Notwehrsituation gedeckt. Indem die Vorinstanz dies verneine, verletze sie <ref-law>. B._, auf dessen Aussagen die Vorinstanz insbesondere abstelle, habe angegeben, er habe versucht, den Beschwerdegegner zurückzuhalten. Dieser habe sich allerdings immer wieder losgerissen und den Beschwerdeführer attackiert. Er habe auch versucht, den Beschwerdegegner zu beruhigen und auf ihn einzureden. Der Beschwerdegegner habe sich jedoch nicht beruhigen lassen. Weiter führt der Beschwerdeführer aus, nachdem er bereits im Auto mit Faustschlägen gegen das Gesicht traktiert worden sei, habe ihn der Beschwerdegegner auch verbal bedroht mit den Worten: "Ich schlag dich auch kaputt, du hast keine Chance". Der Beschwerdegegner sei ihm körperlich klar überlegen gewesen. Den Freunden des Beschwerdegegners sei bekannt gewesen, dass dieser unberechenbar sei, wenn er viel Alkohol getrunken habe. Dann wisse er nicht mehr, was er tue. Aufgrund des Vorwissens um das Temperament des Beschwerdegegners und dessen Verhalten in der fraglichen Nacht, insbesondere des Insistierens und des mehrmaligen Losgehens auf den Beschwerdeführer, habe während der gesamten Zeit eine Notwehrsituation vorgelegen. Als Reaktion darauf habe er ein Messer gezogen und damit vor dem Gesicht des Beschwerdegegners herumgefuchtelt. Er habe in diesem Zeitpunkt jedoch weder auf den Beschwerdegegner eingestochen noch Stichbewegungen in dessen Richtung gemacht. Die Abwehr sei verhältnismässig gewesen und die Schnittverletzung am Ohr des Beschwerdegegners aufgrund der Notwehrlage gerechtfertigt.
1.2.1. Wird jemand ohne Recht angegriffen oder unmittelbar mit einem Angriff bedroht, so ist der Angegriffene oder jeder andere berechtigt, den Angriff in einer den Umständen angemessenen Weise abzuwehren (<ref-law>; "rechtfertigende Notwehr"). Die Abwehr in einer Notwehrsituation muss nach der Gesamtheit der Umstände als verhältnismässig erscheinen. Eine Rolle spielen insbesondere die Schwere des Angriffs, die durch den Angriff und die Abwehr bedrohten Rechtsgüter, die Art des Abwehrmittels und dessen tatsächliche Verwendung. Die Angemessenheit der Abwehr ist auf Grund jener Situation zu beurteilen, in der sich der rechtswidrig Angegriffene im Zeitpunkt seiner Tat befand. Es dürfen nicht nachträglich allzu subtile Überlegungen darüber angestellt werden, ob der Angegriffene sich nicht allenfalls auch mit anderen, weniger einschneidenden Massnahmen hätte begnügen können (<ref-ruling> E. 3.1 und 3.2 mit Hinweisen).
1.2.2. Nach der vorinstanzlichen Einschätzung lag, während der Beschwerdeführer noch im Fahrzeug sass und vom Beschwerdegegner getreten und geschlagen wurde, ein rechtswidriger Angriff vor, der eine Notwehrsituation begründete. Für den Handlungsabschnitt des Herumfuchtelns mit dem Messer habe dann allerdings keine Notwehrsituation mehr vorgelegen. Da die Anwesenden sofort eingegriffen und den Beschwerdegegner zurückgezogen hätten, habe es keinerlei nachvollziehbaren Anlass gegeben, das Messer zu zücken und damit vor dem Gesicht des Beschwerdegegners herumzufuchteln. Erst als der Beschwerdegegner den Beschwerdeführer in den Schwitzkasten nahm, soll erneut eine Notwehrlage begründet worden sein. Daneben führt die Vorinstanz aus, die Kollegen hätten nicht verhindern können, dass der sehr aggressive Beschwerdegegner den ihm körperlich nicht nur leicht, sondern weit unterlegenen Beschwerdeführer in den Schwitzkasten genommen habe. Davon habe sich der Beschwerdegegner auch durch das Herumfuchteln des Beschwerdeführers mit dem Messer und der dabei davongetragenen Verletzung am Ohr nicht abhalten lassen. Vor diesem Hintergrund ist nicht nachvollziehbar, weshalb die Vorinstanz davon ausgeht, die Notwehrsituation sei für kurze Zeit - während des Herumfuchtelns mit dem Messer - unterbrochen worden. Zwar wurde der Beschwerdegegner mehrmals durch das Eingreifen der Kollegen zurückgehalten. Dadurch wurde jedoch nicht die Notwehrsituation an sich beendet. Die vorinstanzliche Annahme, dass im Zeitpunkt, als der Beschwerdeführer das Messer behändigte und damit vor dem Beschwerdegegner herumfuchtelte, um diesen auf Abstand zu halten, kein unmittelbarer Angriff drohte, erscheint nach dem Gesagten widersprüchlich. Die Vorinstanz hätte somit die Notwehrsituation bejahen müssen. Aufgrund der Geringfügigkeit der erlittenen Verletzung war die Abwehrhandlung zudem verhältnismässig. Der Schuldspruch wegen einfacher Körperverletzung mit einem gefährlichen Gegenstand verletzt Bundesrecht. Die Beschwerde erweist sich in diesem Punkt als begründet.
2.
2.1. Hinsichtlich des Messerstichs in den Rücken beanstandet der Beschwerdeführer, auch dabei habe er in rechtfertigender Notwehr im Sinne von <ref-law> gehandelt. Der Beschwerdegegner sei ihm körperlich deutlich überlegen gewesen. Alle hätten gewusst, dass der Beschwerdegegner in alkoholisiertem Zustand unberechenbar sei. Er habe sich aus dem Schwitzkasten allein nicht mehr befreien können. Für ihn sei nicht absehbar gewesen, ob der Beschwerdegegner ihm einen bleibenden körperlichen Schaden zufügen, ihm die Luft ausgehen, er ohnmächtig werden oder sich weitere Verletzungen zuziehen könnte. Nebst seiner Körperkraft sei ihm lediglich noch das Messer zur Verfügung gestanden. Der Einsatz des Messers sei die einzige erfolgversprechende Abwehrhandlung gewesen. Es sei weltfremd, in einer solchen Situation von ihm zu verlangen, dass er sich genau überlege, wohin er mit dem Messer steche.
2.1.1. Die Vorinstanz erwägt, der Beschwerdegegner sei zwar dem Beschwerdeführer weit überlegen und sehr aggressiv gewesen, doch seien mehrere Freunde dabei gewesen und hätten versucht, die beiden auseinanderzubringen. Der Beschwerdeführer sei dem Beschwerdegegner daher nicht schutzlos ausgeliefert gewesen und habe nicht ernsthaft damit rechnen müssen, vom Beschwerdegegner erheblich verletzt zu werden. Er sei denn auch noch nicht verletzt worden. Der Beschwerdeführer habe um die Gefährlichkeit eines Messers, gerade in einem dynamischen Geschehensablauf, gewusst. Der Messereinsatz, insbesondere ein Stich in den Rücken, sei in dieser Situation unverhältnismässig gewesen. Beispielsweise hätte er den Beschwerdegegner auch ins Gesäss stechen können. Die Verhältnismässigkeit der Abwehrhandlung sei zu verneinen.
2.1.2. Zwar dürfen wie dargelegt (vgl. E. 1.2.1) nicht nachträglich allzu subtile Überlegungen darüber angestellt werden, ob der Angegriffene sich nicht allenfalls auch mit anderen, weniger einschneidenden Massnahmen hätte begnügen können und sollen. Bei der Verwendung gefährlicher Werkzeuge ist jedoch praxisgemäss besondere Zurückhaltung geboten, da deren Einsatz stets die Gefahr schwerer oder gar tödlicher Verletzungen mit sich bringt (<ref-ruling> E. 3.3). Der Beschwerdeführer hätte, wie von der Vorinstanz zutreffend ausgeführt, versuchen können, den Beschwerdegegner an einer anderen, weniger gefährlichen Stelle zu treffen. Mit dem unkontrollierten Messerstich in den Rücken des Beschwerdegegners überschritt der Beschwerdeführer die Grenzen der rechtfertigenden Notwehr. Er gefährdete den Beschwerdegegner aufgrund der Nähe der Einstichstelle zur Lunge und zu einer Körperhauptschlagader gemäss Gutachten des Instituts für Rechtsmedizin der Universität Basel (IRM) vom 25. März 2013 erheblich. Die Vorinstanz durfte ohne weiteres davon ausgehen, dass die Gefährlichkeit seines Handelns für den Beschwerdeführer auch in der konkreten Situation mühelos erkennbar war. Indem die Vorinstanz die Unverhältnismässigkeit der Abwehrhandlung bejaht, verletzt sie kein Bundesrecht.
2.2. Im Sinne einer Eventualerwägung führt der Beschwerdeführer aus, er sei vom Beschwerdegegner provoziert worden. Dieser habe sich über sein Stottern lustig gemacht, weshalb er bereits sehr erregt gewesen sei. Dann habe ihn der Beschwerdegegner auch noch auf eine Weise angegriffen, dass er in Panik geraten sei. Er habe die Grenzen der Notwehr in entschuldbarer Aufregung überschritten und deshalb nicht schuldhaft gehandelt (<ref-law>).
2.2.1. Artikel 16 StGB regelt die "entschuldbare Notwehr": Überschreitet der Abwehrende die Grenzen der Notwehr nach Artikel 15, so mildert das Gericht die Strafe (<ref-law>). Überschreitet der Abwehrende die Grenzen der Notwehr in entschuldbarer Aufregung oder Bestürzung über den Angriff, so handelt er nicht schuldhaft (<ref-law>). Ein Notwehrexzess ist gemäss <ref-law> entschuldbar, wenn die Aufregung oder die Bestürzung des Täters allein oder zumindest vorwiegend auf den rechtswidrigen Angriff zurückzuführen ist. Überdies müssen Art und Umstände des Angriffs derart sein, dass sie die Aufregung oder die Bestürzung entschuldbar erscheinen lassen. Nicht jede geringfügige Erregung oder Bestürzung führt zu Straflosigkeit (<ref-ruling> E. 3). Das Gericht hat einen umso strengeren Massstab anzulegen, je mehr die Reaktion des Täters den Angreifer verletzt oder gefährdet (<ref-ruling> E. 3b). Erforderlich ist, dass es dem Täter aufgrund der Aufregung oder Bestürzung über den Angriff nicht möglich war, besonnen und verantwortlich zu reagieren (Urteil 6B_1211/2015 vom 10. November 2016 E. 1.3.2 mit Hinweisen). Insoweit besteht trotz der absoluten Formulierung ein gewisses Ermessen (<ref-ruling> E. 3b; Urteil 6B_810/2011 vom 30. August 2012 E. 5.3.2 mit Hinweisen).
2.2.2. Entgegen der Auffassung des Beschwerdeführers ist nicht zu beanstanden, wenn die Vorinstanz das Vorliegen eines entschuldbaren Notwehrexzesses nach <ref-law> verneint. Die Umstände des Angriffs waren nicht derart, dass sie die Aufregung oder Bestürzung des Beschwerdeführers bei objektiver Betrachtung als entschuldbar erscheinen lassen würden. Hierfür ist, wie bereits erwähnt, ein umso strengerer Massstab anzulegen, je mehr die Reaktion des Täters den Angreifer verletzt oder gefährdet. In casu war der Beschwerdegegner unbewaffnet. Der Beschwerdeführer gefährdete ihn durch den Stich mit dem Messer in den Rücken erheblich. Entsprechend schwerwiegend müsste seine Aufregung oder Bestürzung über den Angriff gewesen sein, um anzunehmen, es wäre ihm nicht möglich gewesen, besonnen und verantwortlich, namentlich mit einem milderen Mittel zu reagieren. Diesbezüglich kann auf die zutreffenden vorinstanzlichen Ausführungen verwiesen werden. Demnach war der Angriff des Beschwerdegegners angesichts des Eingreifens durch die Anwesenden nicht derart bedrohlich und kann die Bestürzung des Beschwerdeführers darüber nicht so gross gewesen sein, dass ein potentiell lebensgefährlicher Messerstich in den Rücken entschuldbar erscheint. Der Übergriff des Beschwerdegegners erfolgte denn auch weder unvermittelt noch überraschend, ging diesem doch eine längere Auseinandersetzung im Innern des Fahrzeugs voraus. Der Beschwerdeführer wusste bereits beim Aussteigen aus dem Auto, dass der Beschwerdegegner aggressiv war, so dass ihn dessen Angriff nicht sonderlich überrascht haben kann. Dass er im Schwitzkatzen in Aufregung geraten ist und in einer gewissen Bestürzung gehandelt hat, ist nachvollziehbar. Dies reicht aber nicht für eine Straflosigkeit der Notwehrüberschreitung, zumal er mit der Behändigung des Messers selbst zur Eskalation der Situation beitrug. Das Mass des Exzesses ist durch die Heftigkeit der Erregung somit nicht gedeckt. Die Vorinstanz überschreitet das ihr zustehende Ermessen nicht.
3.
Die Beschwerde ist teilweise gutzuheissen und im Übrigen abzuweisen. Die Sache ist zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Der Beschwerdeführer wird im Umfang seines Unterliegens kostenpflichtig, während der Kanton Basel-Stadt keine Kosten zu tragen hat (Art. 66 Abs. 1 und 4 BGG). Der Kanton Basel-Stadt hat den Beschwerdeführer im Umfang seines Obsiegens für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Dem Beschwerdegegner ist keine Entsch ädigung zuzusprechen, da ihm im bundesgerichtlichen Verfahren keine Umtriebe entstanden sind.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen, das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 26. Oktober 2016 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen.
2.
Dem Beschwerdeführer werden Gerichtskosten von Fr. 2'000.-- auferlegt.
3.
Der Kanton Basel-Stadt hat dem Beschwerdeführer für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 1'500.-- zu bezahlen.
4.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Dreiergericht, schriftlich mitgeteilt.
Lausanne, 5. Oktober 2017
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Schär