Como tudo nesse ramo depende bastante, eu ja trabalhei com Programacao Orientada a Objeto (POO), e realmente, nao eh pra mim.

Existem varias criticas a serem feitas a POO de uma perspectiva menos pessoal, mas enfim não vem ao caso. Em caso de curiosidade recomendo buscar videos do Rich Hickey criador da linguagem clojure pra mais informaçao, ele traz criticas pertinentes ao OOP e Tipagem statica, de maneira muito mais elaborada e articuladas que eu poderia trazer aqui.

Enfim, Sim, Estrutura de Dados eh um conhecimento mais importante e precede POO, mas nao vejo como um bloqueio direto, pois boas parte dos conceitos de POO nao tem requisitos de estrutura dedos.

POO eh mais uma filosofia de organizacao de software, e estrutura de dados vao sempre estar por baixo desses objetos, maps/hashmaps pra busca chave valor, linked-list pra atravessar item com sequencia, array/vector pra listas onde acesso randomico eh necessario, e sets pra quando se precisa fazer comparacao dos membros de uma lista... alem de muitas implementacoes diferentes de arvores.

Atualmente usando Linguagem Functionais, tem se preferido trabalhar diretamente com as estruturas de dados e nao com objetos que as encapsulam. Eu pessalmente acho que isso traz mto mais sanidade ao projeto, principalmente quando aliado a estruturas de dados imutaveis (outro topico).

Boa sorte na jornada, espero ter ajudado um pouco!